BOJ : 4179 불!

---

[BOJ 4179(G3) 리뷰]

 

지훈이가 미로에 갇혀있다.

미로에 불이나서 불이 1분에 한칸씩 옮겨간다고 한다. 지훈이도 1분에 한칸씩 이동할 수 있다.

주어진 미로에서 지훈이가 과연 탈출할 수 있는지 구하고 탈출한다면 가장 빨리 탈출하는데에 몇초가 걸리는지 구해야한다. 탈출하지 못하면 IMPOSSIBLE을 출력해야한다.

 

입력은 다음과 같이 주어진다.

4 4

####

#JF#

#. .#

#. .#

 

새로운 유형이라 접근방법이 굉장히 어려웠다. 힌트를 보고 풀었다.

문제를 풀기 위해선 먼저 불이 옮겨가는 시간에 대해 탐색을 수행해야 한다.

그 후에 지훈이의 위치로부터 탐색을 시작하자. 지훈이가 가고자하는 위치가 이미 먼저 불이 옮긴 위치라면 그곳으로 이동할 수 없다. 벽을 만나게되면 탈출에 성공한것이므로 거리값을 출력한다.

---

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
using namespace std;

#define X first
#define Y second
string board[1002];
int dist[1002][1002];
int dist2[1002][1002];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	queue <pair<int, int>> Q; //지훈
	queue <pair<int, int>> Q2; //불
	for (int i = 0; i < n; i++)
	{
		cin >> board[i];
	}

	for (int i = 0; i < n; i++)
	{
		fill(dist[i], dist[i] + m, -1);
		fill(dist2[i], dist2[i] + m, -1);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == 'J')
			{
				Q.push({ i,j });
				dist[i][j] = 0;
			}
			if (board[i][j] == 'F')
			{
				Q2.push({ i,j });
				dist2[i][j] = 0;
			}
		}
	}

		while (!Q2.empty()) //불에 대한 BFS
		{
			auto cur = Q2.front();
			Q2.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
				dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
				Q2.push({ nx,ny });
			}
		}

		//지훈이에 대한 BFS 방문하고자 할때 이미 불이 붙었다면 방문 불가함

		while (!Q.empty()) //불에 대한 BFS
		{
			auto cur = Q.front();
			Q.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				{
					cout << dist[cur.X][cur.Y] + 1;
					return 0;
				}
				if (dist[nx][ny] >= 0 || board[nx][ny] == '#') continue;
				if (dist2[nx][ny] != -1 && dist[cur.X][cur.Y] + 1 >= dist2[nx][ny]) continue;
				dist[nx][ny] = dist[cur.X][cur.Y] + 1;
				Q.push({ nx,ny });
			}
		}

		cout << "IMPOSSIBLE";
}