BOJ - 4179번_불!

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다. 지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력하는 프로그램 작성하기

  • 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
  • 불은 각 지점에서 네 방향으로 확산된다.
  • 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
  • 지훈이와 불은 벽이 있는 공간은 통과하지 못한다.


풀이

불이 난 지점부터 BFS를 시작하여 dist1배열에 불이 번지는 시간(거리)을 기록한다. 또한, 지훈이가 있는 지점부터 BFS를 돌며 거리를 기록해 이미 불이 번진 곳이거나 지훈이가 도착할 때 불도 번질 곳이라면 갈 수 없다. 이렇게 진행하며 미로 밖으로 나가게 된다면 탈출 성공이다.


소스코드

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

int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
string board[1005];
int dist1[1005][1005];
int dist2[1005][1005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int R, C;
	cin >> R >> C;
	queue<pair<int,int>> qj;
	queue<pair<int,int>> qf;
	
	for(int i=0; i<R; i++) {
		fill(dist1[i], dist1[i]+C, -1);
		fill(dist2[i], dist2[i]+C, -1);
	}
	
	for(int i=0; i<R; i++) {
		cin >> board[i];
	}
	
	for(int i=0; i<R; i++) {
		for(int j=0; j<C; j++) {
			if(board[i][j]=='F') {
				qf.push({i,j});
				dist1[i][j] = 0;
			}
			if(board[i][j]=='J') {
				qj.push({i,j});
				dist2[i][j] = 0;
			}
		}
	}
	
	while(!qf.empty()) {
		auto cur = qf.front();
		qf.pop();
		for(int k=0; k<4; k++) {
			int nx = cur.first + dx[k];
			int ny = cur.second + dy[k];
			if(nx<0 || nx>=R || ny<0 || ny>=C) continue;
			if(board[nx][ny]=='#' || dist1[nx][ny]>=0) continue;
			dist1[nx][ny] = dist1[cur.first][cur.second]+1;
			qf.push({nx,ny});
		}
	}
	
	while(!qj.empty()) {
		auto cur = qj.front();
		qj.pop();
		for(int k=0; k<4; k++) {
			int nx = cur.first + dx[k];
			int ny = cur.second + dy[k];
			if(nx<0 || nx>=R || ny<0 || ny>=C) {
				cout << dist2[cur.first][cur.second]+1;
				return 0;
			}
			if(board[nx][ny]=='#' || dist2[nx][ny]>=0) continue;
			if(dist1[nx][ny]!=-1 && dist1[nx][ny]<=dist2[cur.first][cur.second]+1) continue;
			dist2[nx][ny] = dist2[cur.first][cur.second]+1;
			qj.push({nx,ny});	
		}
	}
	cout << "IMPOSSIBLE";
}