[BOJ] 백준 5427번 불

링크

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

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

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

입력

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

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

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

'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

 #include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <tuple>

#define X first
#define Y second
using namespace std;
int tc; 
string board[1003];
int dist1[1003][1003];
int dist2[1003][1003];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tc; 
	while (tc--) {
		//초기화 
		for (int i = 0; i < 1003; i++) {
			board[i] = '\0'; 
//문자열의 시작을 널포인트('\0')로 하면 버퍼가 비워지게 된다.
			for (int j = 0; j < 1003; j++) {
				dist1[i][j] = 0;
				dist2[i][j] = 0;
			}
		}

		int n, m;
		cin >> m >> n;
		for (int i = 0; i < n; i++) {
			cin >> board[i];
		}
		
		queue <pair <int, int > > q1; //불에 대한 Queue
		for (int i = 0; i < n; i++) { // 불에 대해서... 
			for (int j = 0; j < m; j++) {
				if (board[i][j] == '*') {
					q1.push({ i, j }); //불의 dist는 0
				}
				else if (board[i][j] != '#') { // 불도 아니고 벽도 아니면 갈 수 있는 길
					dist1[i][j] = -1;
				}
			}
		}
		
		while (!q1.empty()) { //불 bfs
			pair <int, int> cur = q1.front();
			q1.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cur.X + dx[i];
				int ny = cur.Y + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (dist1[nx][ny] >= 0) continue;
				dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
				q1.push({ nx, ny });
			}
		}
		queue <pair <int, int > > q2;  //상근이에 대한 Queue
		for (int i = 0; i < n; i++) { // 상근이에 대해서...
			for (int j = 0; j < m; j++) {
				if (board[i][j] == '@') {
					q2.push({ i, j });
				}
				else if (board[i][j] != '#') { // 상근이도 아니고 벽도 아니면 갈 수 있는 길
					dist2[i][j] = -1;
				}
			}
		}
		bool escape = false;
		while (!q2.empty()) { //상근이 bfs
			auto cur = q2.front();
			q2.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cur.X + dx[i];
				int ny = cur.Y + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
					// 범위를 넘는 다는것은 탈출을 의미
					escape = true;
					break;
				}
				if (dist2[nx][ny] != -1 || (dist1[nx][ny]!=-1 &&dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1)) continue; 
//불의 dist1가 더 작거나 같은면 즉, 불이 먼저 도착하면 그 칸은 못간다. dist1[nx][ny]!=-1 이 조건은 불이 없을경우, 모든 갈 수 있는 칸이 -1로 남아있기 때문에 추가했다.
				dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
				q2.push({ nx, ny });
			}
			if (escape == true) {
				cout << dist2[cur.X][cur.Y] + 1 << '\n';
				break;
			}
		}
		//bfs 탐색을 다 돌아도 탈출을 못한다면 그건 탈출 실패를 의미 , escape는 여전히 false겟지
		if(escape == false ) cout << "IMPOSSIBLE" << '\n';
	}
}

설명

📌 bfs유형 중 "두 종류의 시작점 유형"
불이 상근에게 즉, 한쪽으로만 영향을 주는 유형이므로 불을 먼저 bfs 탐색 해놓고 상근이를 bfs탐색한다. -> dist 배열이 2개 필요 -> 불보다 상근이가 늦게 도착하면 안되고 범위를 벗어나면 탈출!

• 불의 dist1가 dist2보다 더 작거나 같은면 즉, 불이 먼저 도착하면 그 칸은 못간다.
• ⭐ dist1[nx][ny]!=-1 이 조건은 불이 애초에 없을 경우, 모든 갈 수 있는 칸이 -1로 남아있기 때문에 추가했다. -> 이 조건을 빼먹으면 한참 헤맬 수 있다.