[백준-5427] 불


백준에는 불을 피하는 2가지 문제가 있다.

그중 더 어려운 버전의 문제이다.

히든케이스를 계속 잡지 못해서 시간이 오래 걸렸다.

삼성 역량테스트의 바이러스 문제와 비슷한데

불에대한 정보를 담는 fq와 도망가는 사람의 정보를 담는 q를 두어서

두가지 Queue를 만드는 것이 핵심인 것 같다.

Code



#include <iostream>
#include <cstring>
#include <queue>
#define MAX 1001
using namespace std;

int w, h, T;
char building[MAX][MAX];
int check[MAX][MAX];
bool Fire[MAX][MAX];
int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
queue<pair<int, int>> fq;
queue<pair<int, int>> q;

int bfs(int y, int x) {
	q.push(pair<int, int>(y, x));
	check[y][x] = 1;
	while (!q.empty()) {
		int num_of_fire = fq.size();
		while (num_of_fire--) {
			int fire_y = fq.front().first;
			int fire_x = fq.front().second;
			fq.pop();
			for (int i = 0; i < 4; i++) {
				int nf_y = fire_y + dy[i];
				int nf_x = fire_x + dx[i];
				if (nf_y<0 || nf_y >h - 1 || nf_x <0 || nf_x >w - 1) continue;
				if (building[nf_y][nf_x] == '#' || Fire[nf_y][nf_x]) continue;
				fq.push(pair<int, int>(nf_y, nf_x));
				Fire[nf_y][nf_x] = true;
				building[nf_y][nf_x] = '*';
			}
		}

		int run = q.size();
		while (run--) {
			int run_y = q.front().first;
			int run_x = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int ny = run_y + dy[i];
				int nx = run_x + dx[i];
				if (ny<0 || ny >h - 1 || nx <0 || nx >w - 1)
					return check[run_y][run_x];
				if (building[ny][nx] != '.' || check[ny][nx] > 0) continue;
				q.push(pair<int, int>(ny, nx));
				check[ny][nx] = check[run_y][run_x] + 1;
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		memset(Fire, 0, sizeof(Fire));
		memset(building, 0, sizeof(building));
		memset(check, 0, sizeof(check));
		while (!q.empty()) q.pop();
		while (!fq.empty()) fq.pop();
		int answer = 0;
		scanf("%d %d", &w, &h);
		int start_y, start_x;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> building[i][j];
				if (building[i][j] == '@') {
					start_y = i, start_x = j;
				}

				if (building[i][j] == '*' && !Fire[i][j]) {
					fq.push(pair<int, int>(i, j));
					Fire[i][j] = true;
				}
			}
		}


		answer = bfs(start_y, start_x);
		if (answer == -1) printf("IMPOSSIBLE\n");
		else printf("%d\n", answer);

	}
	return 0;
}





© 2020. by Andyworkingholiday

Powered by aiden