백준 4179 불!

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 지훈이가 불을 피해 미로를 탈출할 수 있는 가장 빠른 시간을 출력하는 문제입니다.

 

이 문제는 지훈이도 이동을 하지만 불또한 상하좌우로 벽이 없는곳은 확산이 되므로 bfs를 통해서 불과 지훈이 모두를 이동시켜 주어야합니다.

 

벽이 있는 부분은 visited배열에 방문 불가능으로 설정해놓고 먼저 불을 확산시킵니다. 그이후 지훈이가 이동을 하는데 지훈이가 방문한 지점은 2로 설정합니다. 그 이유는 지훈이가 방문한 길은 지훈이는 재방문이 불가능하지만 불은 방문이 가능하기 때문입니다. 따라서 지훈이는 visited가 1,2인 지점이 방문 불가능하고 불은 visited가 1인지점만 방문이 불가능하도록 설정해주며 bfs를 돌면 지훈이의 탈출여부를 확인 할 수 있습니다.

 

다음은 코드입니다.

 

 

#include <iostream>
#include <string>
#include <queue>

using namespace std;
 
char maze[1001][1001];
int R,C;
int visited[1001][1001];
int nextx[4] = {1, 0, -1, 0};
int nexty[4] = {0, 1, 0, -1};
queue<pair<int, int>> jq;
queue<pair<int, int>> fq;
bool flag = false;
int num;
 
void bfs() {

	while(!jq.empty()) {
		int lenj = jq.size();
		int lenf = fq.size();
		
		if(!fq.empty()) {
		for(int j = 0; j < lenf; j++) {
			for(int i = 0; i < 4; i++) { //불 확산 
				int x = fq.front().first + nextx[i];
				int y = fq.front().second + nexty[i];
				
				if(x < 0 || x >= R || y < 0 || y >= C)
					continue;

				if(visited[x][y] == 0 || visited[x][y] == 2) {
					fq.push(make_pair(x, y));
					visited[x][y] = 1;
				}
			}
			fq.pop();
		}
		}
		
		for(int j = 0; j < lenj; j++) {
			for(int i = 0; i < 4; i++) { //지훈이 
				int x = jq.front().first + nextx[i];
				int y = jq.front().second + nexty[i];
	
				if(x < 0 || x >= R || y < 0 || y >= C) {
					flag = true;
					num++;
					return;
				}
					 
				if( visited[x][y] == 0 ) {
					jq.push(make_pair(x, y));
					visited[x][y] = 2;
				}
			}
			jq.pop();
		}
		num++;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> R >> C;
	int jx,jy;
	int fx = -1;
	int fy = -1;

	for(int i = 0; i < R; i++) {
		string str;
		cin >> str;
		for(int j = 0; j < C; j++) {
			maze[i][j] = str[j];
			if(str[j] == '#')
				visited[i][j] = 1;
			
			if(str[j] == 'F') {
				visited[i][j] = 1;
				fq.push(make_pair(i, j));			
			}
			
			if(str[j] == 'J') {
				visited[i][j] = 2;
				jq.push(make_pair(i, j)); 
			}
		}
	}

	bfs();

	if(flag)
		cout<<num;
	else
		cout<<"IMPOSSIBLE";

	return 0;
}