백준 4179번: 불!

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

4179번: 불!

 

 

0. 알고리즘 분류

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

 

 

1. 문제

 

 

2. 풀이

 BFS 문제이지만, 여태까지 풀었던 기본적인 문제와는 조금 다르다. 불과 사람에게 각각 BFS를 취해주어야 한다. 어려운 점은 같은 스텝에서 같이 BFS를 돌려야한다는 점이다. 나는 문제를 복잡하게 생각하는 바람에 푸는데 12시간이나 걸렸다...

 

 불이 붙는 좌표를 우선적으로 BFS를 돌린 후, 사람이 갈 수 있는 좌표를 BFS를 돌린다. 이 작업을 사람이 탈출하거나, 움직일 수 있는 경로가 없어질 때까지 반복한다.

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

struct pos {
	int x, y;
};

int r, c;
char maps[1001][1001];
bool noWay[1001][1001];
pos J;
queue<pos> q2;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(void) {
	scanf(" %d %d", &r, &c);
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			scanf(" %c", &maps[i][j]);
			if (maps[i][j] == 'J') {
				J = {j,i};
				maps[i][j] = '.';
			}
			else if (maps[i][j] == 'F') {
				q2.push({j,i});
			}
			else if (maps[i][j] == '#') {
				noWay[i][j] = true;
			}
		}
	}
	
	// bfs
	int cnt = 0;
	queue<pos> q;
	q.push({J.x, J.y});
	noWay[J.y][J.x] = true;
	
	while (!q.empty()) {
		int m = q2.size();
		for (int j = 0; j < m; j++) {
			pos cf = q2.front();
			q2.pop();
			
			for (int i = 0; i < 4; i++) {
				pos nf = {cf.x + dx[i], cf.y + dy[i]};
				if (0 <= nf.x && nf.x < c && 0 <= nf.y && nf.y < r) {
					if (maps[nf.y][nf.x] == '.' || maps[nf.y][nf.x] == 'J') {
					q2.push(nf);
					maps[nf.y][nf.x] = 'F';
					}
				}
			}
		}
		
		int n = q.size();
		for (int j = 0; j < n; j++) {
			pos cur = q.front();
			q.pop();
			
			if (0 == cur.x || cur.x == c-1 || 0 == cur.y || cur.y == r-1) {
				printf("%d\n", cnt+1);
				return 0;
			}
			
			for (int i = 0; i < 4; i++) {
				pos n = {cur.x + dx[i], cur.y + dy[i]};
				
				if (0 > n.x || n.x >= c || 0 > n.y || n.y >= r) {
					continue;
				}
			
				if (maps[n.y][n.x] == '.' && !noWay[n.y][n.x]) {
					q.push(n);
					maps[n.y][n.x] = 'J';
					noWay[n.y][n.x] = true;
				}
			}
		}
		
		cnt++;
	}
	
	printf("IMPOSSIBLE\n");
	return 0;
}