[백준 4179] 불! (C++)

https://www.acmicpc.net/problem/4179

4179번: 불!

문제

---

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

---

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

---

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

문제 풀이

---

BFS를 이용한 문제.

불과 지훈이는 문제 상 동시에 이동하지만 구현할 때에는 동시에 이동할 수 없다. 어느쪽을 먼저 이동하는지는 상관이 없으며, 나는 불을 먼저 이동시키고 지훈이를 이동시켰다.

불의 최소 이동거리보다 빨리 지훈이가 도착할 수 있다면 지훈이가 이동할 수 있는 공간이며, 큐가 다 비워질 때까지 탈출을 못하면 탈출 경로가 불에 막혀 아예 탈출할 수 없다. 그 이전에 배열의 맨끝에 도착하면 탈출할 수 있다.

#include <iostream>
#include <queue>
using namespace std;
int N, M;
char** arr;
bool** isVisited;
int** fireMove;
int initJX, initJY;
struct info
{
	int x;
	int y;
	int length;
	info(int a, int b, int c)
	{
		x = a;
		y = b;
		length = c;
	}
};
queue<info> bfsQueue;

void moveFire(int initFireX, int initFireY)
{
	fireMove[initFireX][initFireY] = 0;
	bfsQueue.push(info(initFireX, initFireY, 0));
	while (!bfsQueue.empty())
	{
		info current = bfsQueue.front();
		fireMove[current.x][current.y] = current.length;
		if (current.x > 0 && current.length+1 < fireMove[current.x-1][current.y] && arr[current.x - 1][current.y] != '#')
		{
			fireMove[current.x-1][current.y] = current.length;
			bfsQueue.push(info(current.x - 1, current.y, current.length+1));
		}
		if (current.x < N-1 && current.length + 1 < fireMove[current.x + 1][current.y] && arr[current.x + 1][current.y] != '#')
		{
			fireMove[current.x+1][current.y] = current.length;
			bfsQueue.push(info(current.x + 1, current.y, current.length+1));
		}
		if (current.y > 0 && current.length + 1 < fireMove[current.x][current.y-1] && arr[current.x][current.y-1] != '#')
		{
			fireMove[current.x][current.y-1] = current.length;
			bfsQueue.push(info(current.x, current.y - 1, current.length+1));
		}
		if (current.y < M-1 && current.length + 1 < fireMove[current.x][current.y+1] && arr[current.x][current.y + 1] != '#')
		{
			fireMove[current.x][current.y+1] = current.length;
			bfsQueue.push(info(current.x, current.y + 1, current.length+1));
		}
		bfsQueue.pop();
	}
}

void moveJihoon()
{
	isVisited[initJX][initJY] = true;
	bfsQueue.push(info(initJX, initJY, 0));
	bool canEscape = false;
	while (!bfsQueue.empty())
	{
		info current = bfsQueue.front();
		if (current.x == 0 || current.y == 0 || current.x==N-1 || current.y == M-1)
		{
			canEscape = true;
			cout << current.length + 1 << "\n";
			break;
		}
		if (current.x > 0 && isVisited[current.x - 1][current.y] == false && arr[current.x - 1][current.y] != '#' && current.length + 1 < fireMove[current.x-1][current.y])
		{
			isVisited[current.x - 1][current.y] = true;
			bfsQueue.push(info(current.x - 1, current.y, current.length + 1));
		}
		if (current.x < N - 1 && isVisited[current.x + 1][current.y] == false && arr[current.x + 1][current.y] != '#' &&current.length + 1 < fireMove[current.x + 1][current.y])
		{
			isVisited[current.x + 1][current.y] = true;
			bfsQueue.push(info(current.x + 1, current.y, current.length + 1));
		}
		if (current.y > 0 && isVisited[current.x][current.y - 1] == false && arr[current.x][current.y - 1] != '#' && current.length + 1 < fireMove[current.x][current.y-1])
		{
			isVisited[current.x][current.y - 1] = true;
			bfsQueue.push(info(current.x, current.y - 1, current.length + 1));
		}
		if (current.y < M - 1 && isVisited[current.x][current.y + 1] == false && arr[current.x][current.y + 1] != '#' && current.length + 1 < fireMove[current.x][current.y+1])
		{
			isVisited[current.x][current.y + 1] = true;
			bfsQueue.push(info(current.x, current.y + 1, current.length + 1));
		}
		bfsQueue.pop();
	}
	if (canEscape == false)
	{
		cout << "IMPOSSIBLE" << "\n";
	}
}

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

	cin >> N>>M;
	arr = new char*[N];
	isVisited = new bool*[N];
	fireMove = new int*[N];

	for (int i = 0; i < N; i++)
	{
		arr[i] = new char[M];
		isVisited[i] = new bool[M];
		fireMove[i] = new int[M];
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			isVisited[i][j] = false;
			fireMove[i][j] = 100000000;
			if (arr[i][j] == 'J')
			{
				initJX = i;
				initJY = j;
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] == 'F')
			{
				moveFire(i, j);
			}
		}
	}

	moveJihoon();
	return 0;
}