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

문제 링크

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

 

문제 정보

입력

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

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

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

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

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

출력

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

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

 

풀이

 이 문제는 BFS의 응용 문제로 시작점이 두 종류일 때 해결하는 문제이다. 시작점이 두 종류일 경우에 불에 대한 BFS와 지훈이에 대한 BFS를 둘 다 돌려서 해결할 수 있다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

string board[1002];
int dist1[1002][1002]; // 불의 전파 시간을 저장한 배열
int dist2[1002][1002]; // 지훈이의 이동 시간을 저장한 배열
int r, c;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 }; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		fill(dist1[i], dist1[i] + c, -1); // 배열을 미리 -1로 초기화해두면 vis 배열을 따로 둬서 방문 여부를 확인할 필요가 없다!
		fill(dist2[i], dist2[i] + c, -1); // 배열을 미리 -1로 초기화해두면 vis 배열을 따로 둬서 방문 여부를 확인할 필요가 없다!
	}
	
	for (int i = 0; i < r; i++) {
		cin >> board[i];
	}
	
	queue<pair<int, int>> Q1; // 불에 대한 BFS
	queue<pair<int, int>> Q2; // 지훈이에 대한 BFS
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (board[i][j] == 'F') { // 불의 시작 좌표
				Q1.push({i, j});
				dist1[i][j] = 0;
			}
			if (board[i][j] == 'J') { // 지훈이의 시작 좌표
				Q2.push({i, j});
				dist2[i][j] = 0;
			}
		}
	}
	
	// 불에 대한 BFS
	while (!Q1.empty()) {
		auto cur = Q1.front();
		Q1.pop();
		
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			
			if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
				continue;
			}
			if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') {
				continue;
			}
			
			dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
			Q1.push({nx, ny});
		}
	}
	
	// 지훈이에 대한 BFS
	while (!Q2.empty()) {
		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 >= r || ny < 0 || ny >= c) {
				// 범위를 벗어났다는 것은 미로를 탈출 했다는 것!
				cout << dist2[cur.X][cur.Y] + 1;
				return 0;
			}
			if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') {
				continue;
			}
			// 불이 먼저 도착했으면 지훈이는 못지나감!
			if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) {
				continue;
			}
			
			dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
			Q2.push({nx, ny});
		}
	}
	
	cout << "IMPOSSIBLE";
	
	return 0;
}