백준 4179번 - 불!

4179번: 불! (acmicpc.net)

 

미로에서 일하는 지훈이에게 미로에 불이나는 상황이 발생한다.

입력 첫줄에 미로의 행(R) / 미로의 열 (C) 가 주어진다.

 

' # '  - 벽 

 ' . '  -  지나갈 수 있는 공간

' J ' - 지훈이의 초기 위치

' F ' - 불이 난 공간

 

불은 매 분마다 한칸씩 네 방향(상,하,좌,우)으로 확산되며, 지훈이와 붙은 벽을 통과하지 못한다.

지훈이가 탈출 가능하다면 가장 빠른 탈출시간을, 탈출을 못하고 타죽는다면 IMPOSSIBLE을 출력하면 된다.

 

#include<iostream>
#include<queue>
#include<utility>

using namespace std;

//미로
string maze[1001];

//불이 옮겨가는 시간
int Ftime[1001][1001];
//지훈이가 이동하는 시간
int Jtime[1001][1001];

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

int r, c;

pair<int, int> jh;
pair<int, int> fire;


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	queue<pair<int, int>> Q;

	cin >> r >> c;

	//미로의 구성을 입력받고 걸리는 시간 배열들을 -1로 초기화
	for (int i = 0; i < r; i++)
	{
		cin >> maze[i];
		fill(Ftime[i], Ftime[i] + c, -1);
		fill(Jtime[i], Jtime[i] + c, -1);
	}

	//지훈이와 불의 초기위치 세팅 , 불의 위치는 큐에 넣어줌
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (maze[i][j] == 'F')
			{
				fire = { i,j };
				Ftime[i][j] = 0;
				Q.push(fire);
			}
			else if (maze[i][j] == 'J')
			{
				jh = { i,j };
				Jtime[i][j] = 0;
			}			
		}
	}


	//불이 확산하는 시간을 알기위해 bfs돌림
	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int x = cur.first + dx[i];
			int y = cur.second + dy[i];

			//인덱스를 벗어났다면 컨티뉴
			if (x < 0 || y < 0 || y >= c || x >= r) continue;
			//벽이거나 이미 방문한 칸이라면 컨티뉴
			if (maze[x][y] == '#' || Ftime[x][y] >= 0) continue;

			Ftime[x][y] = Ftime[cur.first][cur.second] + 1;
			Q.push({ x,y });
		}
	}

	//지훈이의 위치 push
	Q.push(jh);

	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		
		for (int i = 0; i < 4; i++)
		{
			int x = cur.first + dx[i];
			int y = cur.second + dy[i];

			//인덱스를 벗어났다면 탈출성공
			if (x < 0 || y < 0 || y >= c || x >= r)
			{
				cout << Jtime[cur.first][cur.second] + 1;
				return 0;
			}

			//벽이거나 이미 방문한 칸이라면 컨티뉴
			if (maze[x][y] == '#' || Jtime[x][y] >= 0) continue;
			//현재 탐색하는 칸이 지훈이의 이동보다 불이 빨리 확산되어 죽는 칸이라면 컨티뉴
			if (Ftime[x][y] != -1 && Ftime[x][y] <= Jtime[cur.first][cur.second] + 1) continue;

			Jtime[x][y] = Jtime[cur.first][cur.second] + 1;
			Q.push({ x,y });
		}
	}

	//지훈이의 죽음
	cout << "IMPOSSIBLE";

	return 0;
}

 

이번엔 남의 코드를 참고하지 않고 풀이 힌트를 몇 개를 듣고 풀었다.

 

처음에는 '지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다' 라는게 뭔말인지 이해가 안가서 지훈이쪽 bfs를 돌릴때 상하좌우에 갈곳이 없으면 탈출이 불가능 하다고 생각해 bool 값을 두고 실패를 판단했는데,

 

여러 테스트를 돌려보니 성공할때 인덱스가 넘어가는 부분에서 성공한다는것을 발견하고 다지우고 다시 짰다.

 

일단 Ftime,Jtime이라는 시간을 저장하는 배열을 선언하고 BFS를 두번 돌린다.

불의 위치에서 bfs를 시작하여 불의 확산 시간을 다 저장하고, 지훈이 쪽 bfs를 돌릴때 지훈이의 이동 시간과 이미 저장해놓은 불의 확산 시간을 검사해서 판단했다.

(//현재 탐색하는 칸이 지훈이의 이동보다 불이 빨리 확산되어 죽는 칸이라면 컨티뉴 <- 이 부분)

 

bfs도 이런저런 문제 유형이 많은데 문제를 만날때마다 늘 새롭다 

정말 많이 풀어봐야 늘 것 같다..

 

몇번만에 맞은건지..