[C++] 백준(BOJ) - 4179 : 불!

25 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 4179 : 불!(링크)

알고리즘

1. 그래프 이론
2. 완전탐색
3. BFS

풀이

1. 가중치가 같은 그래프에서 최단 거리를 찾기 - BFS
2. 불을 BFS에 따라 이동 시켜서 불의 최소 시간 이동거리를 모두 구한 fVisited 배열을 만들고, 사람의 최소 시간 이동거리를 구한 후 fVisited의 값과 비교하여 이동 시킬지 말지 정한다
3. 예외처리
   • 불이 없는 경우를 확인하기 위해 INF 값으로 fVisited 배열을 초기화
4. memset 함수는 1바이트 단위로 값을 초기화 하는 함수
   • 0이나 char 타입이 아닌 값으로는 초기화 되지 않는다
   • fill(int *_first, int *_last, const int &val) 함수를 사용!

코드

// BOJ-4179 : 불!
#include<bits/stdc++.h>
using namespace std;

const int INF = 2147000000;

const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

int r, c, jy, jx, ans = -1;
char a[1004][1004];
int fVisited[1004][1004], jVisited[1004][1004];

queue<pair<int,int>> q;

void jbfs(int y, int x)
{
	q.push({ y,x });
	jVisited[y][x] = 1;

	while (q.size())
	{
		pair<int, int> tmp = q.front();
		q.pop();

		if (tmp.first == 0 || tmp.second == 0 || tmp.first == r - 1 || tmp.second == c - 1)
		{
			ans = jVisited[tmp.first][tmp.second];
			return;
		}

		for (int i = 0; i < 4; i++)
		{
			int ny = tmp.first + dy[i];
			int nx = tmp.second + dx[i];

			if (ny < 0 || nx < 0 || ny >= r || nx >= c || a[ny][nx] == '#') continue;
			if (jVisited[ny][nx]) continue;
			if (jVisited[tmp.first][tmp.second] + 1 >= fVisited[ny][nx]) continue;

			jVisited[ny][nx] = jVisited[tmp.first][tmp.second] + 1;
			q.push({ ny,nx });
		}
	}
	return;
}

void fbfs(int y, int x)
{
	while (q.size())
	{
		pair<int, int> tmp = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = tmp.first + dy[i];
			int nx = tmp.second + dx[i];

			if (ny < 0 || nx < 0 || ny >= r || nx >= c || a[ny][nx] == '#') continue;
			if (fVisited[ny][nx] != INF) continue;
			fVisited[ny][nx] = fVisited[tmp.first][tmp.second] + 1;
			q.push({ ny,nx });
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> r >> c;
	
	// 불이 아예 없을 때의 반례 체크
    //memset(fVisited, INF, sizeof(fVisited)); X => 1바이트 단위로 값을 초기화 하는 함수 0이나 char 타입이 아닌 값으로는 초기화 되지 않는다
	fill(&fVisited[0][0], &fVisited[0][0] + 1004 * 1004, INF);

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> a[i][j];

			// 불이 여러개 들어올 수도 있다
			if (a[i][j] == 'F')
			{
				q.push({ i,j });
				fVisited[i][j] = 1;
			}
			else if (a[i][j] == 'J')
			{
				jy = i;
				jx = j;
			}
		}
	}

	fbfs(q.front().first, q.front().second); // 가중치가 같은 그래프의 최단 거리 구하기
	jbfs(jy, jx);

	if (ans != -1) cout << ans << '\n';
	else cout << "IMPOSSIBLE" << '\n';

	return 0;
}

평가

• 문제를 풀이 할 때 단계별로 알고리즘을 만들어 나가기
• 예외처리에 관한 내용을 고려하기
• memset 함수는 1바이트 단위로 초기화 하기 때문에 0이나 char형이 아닌 값으로 초기화 할 때는 fill 함수를 사용하기