백준 5427번: 불 (C++)

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

5427번: 불

 

두 가지를 동시에 신경써야 했다. 불의 확산과 사람의 이동.

 

특히 신경써야 할 부분은

 

1. 이제 불이 붙으려는 칸으로 이동할 수 없다

2. 현재 위치로 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

 

이 두가지이다.

 

 

기본적인 접근은 불을 먼저 확산시킬 것인가, 사람을 먼저 움직일 것인가를 결정하는 것이다.

 

1. 불의 확산 이후 사람의 이동

불을 먼저 확산시키면 사람의 위치가 지워질 가능성이 높다. 따라서 사람의 시작 위치를 미리 관리해주어야 한다.

 

이후에는 사람의 이동거리(매 초 사람의 위치)를 따로 둘 것이기 때문에 초반에 불의 이동에 의해서 @의 위치가 손실되는 것만 신경써주면 이후로는 신경쓸 부분이 없다. 즉 위에서 신경써야 할 부분이라고 언급한 2번 조건이 상관 없어지는 것이다.

 

당연하게도 불을 먼저 확산시켰으므로 불이 붙으려는 칸으로는 당연하게 이동할 수 없다. 구현을 그렇게 했으니까.

 

 

2. 사람의 이동 이후 불의 확산

이 방식은 먼저 사람의 이동을 고려한다. 당연하게도 이동하려는 곳은 비어있는(불도 벽도 아닌) 곳이어야 한다.

 

그리고 그 이동하려는 곳의 4방향을 미리 탐색해서 불이 있는지 없는지를 확인해야 한다. 이것으로 신경써야 할 부분 1을 피할 수 있다.

 

즉 사람의 이동을 구현하는 데에 두 단계가 필요하다는 것이다.

 

또한 사람의 이동을 먼저 구현했기 때문에, 이미 이동한 뒤에 불이 확산하는 것이므로 원래 사람이 있던 자리에 불이 번지는 것은 이제 상관이 없어진다. 이렇게 신경써야 할 부분 2를 해결할 수 있다.

 

 

두 가지 모두 생각해 본 결과, 1의 구현이 더 간단한 것 같았으므로 1번으로 구현 방향을 잡았다.

 

#include<iostream>
#include<queue>
using namespace std;
int Col, Row, dis[1001][1001]; //dis로 사람의 매초 위치(그 지점까지 최단거리)를 관리
char m[1001][1001]; //빌딩 상태
bool Fire[1001][1001]; //불의 존재 여부 관리
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
queue<pair<int, int> > fireQ; //불의 번짐을 관리할 큐
queue < pair<int, int> > q; //사람의 이동을 관리할 큐
void Fbfs() {
	while (!q.empty()) { //사람이 움직일 위치가 없으면 더 이상의 진행이 무의미

		int num = fireQ.size(); //매 초 있던 불꽃으로만 확산 진행
		while (num--) { 
			pair<int, int> cur = fireQ.front();
			fireQ.pop();
			for (int i = 0; i < 4; i++) {
				int nr = cur.first + dr[i];
				int nc = cur.second + dc[i];
				if (nr < 0 || nc < 0 || nr >= Row || nc >= Col) continue;
				if (m[nr][nc] == '#' || Fire[nr][nc]) continue; //벽 or 이미 불이 존재하는 곳이면 continue
				//printf("\n%d %d 추가\n", nr, nc);
				fireQ.push({ nr, nc });
				Fire[nr][nc] = true;
				m[nr][nc] = '*';
			}
		}

		int Run = q.size(); //불과 마찬가지로 매초 한칸씩 움직이게 통제
		while (Run--) {
			pair<int, int> cur = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nr = cur.first + dr[i];
				int nc = cur.second + dc[i];
				if (nr < 0 || nc < 0 || nr >= Row || nc >= Col) {
					//탈출처리 -> 건물 끝까지 가는데 n초 걸렸고, 이제 넘어가니까 +1
					cout << dis[cur.first][cur.second] + 1 << '\n';
					return;
				}
				if (dis[nr][nc] >= 0 || m[nr][nc] != '.')continue; //이미 지나온 길이거나 이동할 수 있는 길이 아니면 continue
				q.push({ nr, nc });
				dis[nr][nc] = dis[cur.first][cur.second] + 1;
			}
		}
	}
	cout << "IMPOSSIBLE" << '\n';
}
void init() {
	for (int i = 0; i < Row; i++) {
		for (int j = 0; j < Col; j++) {
			dis[i][j] = -1; // 0이상이면 사람이 거쳐간 상태(방문 완료)
			Fire[i][j] = false;
 		}
	}
	while (!q.empty()) q.pop(); //탈출 조건에서 큐가 비지 않았는데 함수가 종료됨
	while (!fireQ.empty()) fireQ.pop();
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> Col >> Row;
		
		init(); //TC가 여러개, 큐를 완전히 비우지 않고 끝내는 경우도 있으므로 큐도 초기화
		for (int i = 0; i < Row; i++) {
			for (int j = 0; j < Col; j++) {
				cin >> m[i][j];
				if (m[i][j] == '@') { //사람의 시작 위치를 담아둬야함. 불이 덮어 쓰기 때문에
					q.push({ i, j }); 
					dis[i][j]++;
				}
			}
		}
		

		for (int i = 0; i < Row; i++) {
			for (int j = 0; j < Col; j++) {
				if (m[i][j] == '*' && !Fire[i][j]) {
					fireQ.push({ i, j });
					Fire[i][j] = true;
				}
			}
		}
		Fbfs();
	}
	return 0;
}