백준 5427 불 c++ (bf)

문제 출처 : https://www.acmicpc.net/problem/5427

5427번: 불

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

2021.07.26 - [알고리즘/백준] - 백준 4179 불! c++(bfs)

 

위의 문제와 같은 문제인데 테스트케이스만 추가되었다.

이번엔 fire_map을 만들어 불이 번지는 시간을 모두 저장해놓는 방식 대신,

상근이가 한 번 4방향으로 움직일 때, 불을 먼저 4방향으로 움직여서 불이 번진 곳은 벽으로 표현해놓고,

상근이가 갈 수 있는지 없는지 판단하는 방식으로 풀었다.

이 풀이에선, 불과 상근이가 4방향으로 움직이기 전에, 큐의 사이즈를 저장해놓고, 큐의 사이즈만큼 탐색을 한 이후,

새로 큐에 추가된 사이즈만큼 4방향으로 움직여 준다. 이는 불과 상근이의 모든 움직임을 1초마다 제어하기 위함이다.

코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
char graph[1000][1000];
bool visited[1000][1000];
int R, C;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

void bfs(int r, int c, vector<pair<int, int>> fire) {

	queue<pair<int, int>> startQ;
	queue<pair<int, int>> fireQ;
	int cnt = 0;
	startQ.push({ r,c });
	for (int i = 0; i < fire.size(); i++) {
		fireQ.push({ fire[i].first,fire[i].second });
	}

	while (!startQ.empty()) {
		//fire먼저
		int fqSize = fireQ.size();
		for (int i = 0; i < fqSize; i++) {
			int cr = fireQ.front().first;
			int cc = fireQ.front().second;
			fireQ.pop();
			for (int j = 0; j < 4; j++) {
				int nr = cr + dir[j][0];
				int nc = cc + dir[j][1];
				if (nr >= 0 && nr < R && nc >= 0 && nc < C && graph[nr][nc] != '#') {
					graph[nr][nc] = '#';
					fireQ.push({ nr,nc });
				}
			}
		}
		//상근이 이동
		int sqSize = startQ.size();
		cnt++;
		for (int i = 0; i < sqSize; i++) {
			int cr = startQ.front().first;
			int cc = startQ.front().second;
			startQ.pop();
			for (int j = 0; j < 4; j++) {
				int nr = cr + dir[j][0];
				int nc = cc + dir[j][1];
				if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
					cout << cnt<<'\n';
					return;
				}
				if (nr >= 0 && nr < R && nc >= 0 && nc < C && graph[nr][nc] != '#' && !visited[nr][nc]) {
					startQ.push({ nr,nc });
					visited[nr][nc] = true;
				}
			}
		}
	}
	
	cout << "IMPOSSIBLE"<<'\n';


}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		cin >> C >> R;
		int r, c;
		vector<pair<int, int>> fire;
		//input
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				cin >> graph[i][j];
				if (graph[i][j] == '*') {
					fire.push_back({ i,j });
					
					graph[i][j]='#';
				}
				else if (graph[i][j] == '@') {
					r = i;
					c = j;
				}
			}
		}
		//solve
		bfs(r, c, fire);
	
		//reset
		memset(graph, ' ', sizeof(graph));
		memset(visited, false, sizeof(visited));
	}

	return 0;
}