불

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

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다.

건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다.

벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다.

상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.

상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• ‘.’: 빈 공간
• ‘#’: 벽
• ‘@’: 상근이의 시작 위치
• ‘*’: 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다.

빌딩을 탈출할 수 없는 경우에는 “IMPOSSIBLE”을 출력한다.

예제 입력 1

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번

• 문제의 오타를 찾은 사람: adh0463
• 데이터를 추가한 사람: b8goal, djm03178
• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

통과된 코드

해당 좌표에 불이 언제 도착하는지 먼저 BFS 탐색을 이용하여 확인하고

상근이의 위치에서 BFS 탐색을 이용하여 출구를 찾는다.

#include <iostream>
#include <queue>

using namespace std;

int _T, _W, _H, _Res;
pair<int, int> _CntPos;
int _Map[1002][1002];
bool _IsVisted[1002][1002], _Check;
string _TStr;
// 상, 하, 좌, 우
int _DxDy[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _T;
	while (_T-- > 0) {
		cin >> _W >> _H;
		queue<pair<int, int>> _FireQueue;
		_Check = false;
		for (int i = 1; i <= _H; i++) {
			cin >> _TStr;
			for (int j = 1; j <= _W; j++) {
				if (_TStr[j - 1] == '@') _CntPos = make_pair(i, j);
				else if (_TStr[j - 1] == '*') {
					_Map[i][j] = 1;
					_FireQueue.push(make_pair(i, j));
				}
				else if (_TStr[j - 1] == '#')
					_Map[i][j] = -1;
			}
		}

		while (!_FireQueue.empty()) {
			pair<int, int> _CntFirePos = _FireQueue.front();
			_FireQueue.pop();
			for (int i = 0; i < 4; i++) {
				int _dx = _CntFirePos.first + _DxDy[i][0];
				int _dy = _CntFirePos.second + _DxDy[i][1];
				// 이미 불이 있거나 벽이면 넘어간다.
				if (_Map[_dx][_dy] == -1) continue;
				if (_Map[_dx][_dy] > 0) continue;
				// 범위를 벗어나는 경우 넘어간다.
				if (_dx > _H || _dx <= 0 || _dy > _W || _dy <= 0) continue;
				_Map[_dx][_dy] = _Map[_CntFirePos.first][_CntFirePos.second] + 1;
				_FireQueue.push(make_pair(_dx, _dy));
			}
		}

		// 순서, x, y
		queue< pair<int, pair<int, int>>> _BFSQueue;
		_BFSQueue.push(make_pair(1, _CntPos));
		_IsVisted[_CntPos.first][_CntPos.second] = true;
		while (!_BFSQueue.empty()) {
			int _cnt = _BFSQueue.front().first;
			pair<int, int> _cntPos = _BFSQueue.front().second;
			_BFSQueue.pop();
			for (int i = 0; i < 4; i++) {
				int _dx = _cntPos.first + _DxDy[i][0];
				int _dy = _cntPos.second + _DxDy[i][1];
				// 벽이거나 해당 칸에 불이 붙는 순서와 비교하여 갈 수 없으면 넘어간다.
				if (_Map[_dx][_dy] == -1 || (_Map[_dx][_dy] <= _cnt + 1 && _Map[_dx][_dy] != 0) || _IsVisted[_dx][_dy]) continue;
				// 탈출에 성공하는 경우
				if (_dx > _H || _dx <= 0 || _dy > _W || _dy <= 0) {
					_Res = _cnt;
					_Check = true;
					break;
				}

				_BFSQueue.push(make_pair(_cnt + 1, make_pair(_dx, _dy)));
				_IsVisted[_dx][_dy] = true;
			}
			if (_Check)
				break;
		}

		if (_Check) cout << _Res << "\n";
		else cout << "IMPOSSIBLE" << "\n";

		// 초기화
		for (int i = 1; i <= _H; i++) {
			for (int j = 1; j <= _W; j++) {
				_Map[i][j] = 0;
				_IsVisted[i][j] = false;
			}
		}
	}

	return 0;
}