백준 5427: 불

문제 요약

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

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

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀 수 있는 문제이다. 큐를 두개 준비해서 각 레벨마다 불과 상근이의 위치를 옮겨주면 된다.

메모리 초과가 나와서 int를 short로 바꾸는 등 여러가지를 시도해 보았으나 해결되지 않았다. 그러던 중, 불의 위치를 BFS하던 와중에 기존에 불이 지나갔던 곳을 다시 한번 지나가서 같은 값이 큐에 push되는 일이 발생되는 것을 보았고, if문을 내부에 코드를 추가하여 막아주었더니 해결되었다. (ary[f][s - 1] != '*')

BFS하다가 상근이의 위치가 이동할 곳이 없으면 자동으로 답은 false가 되고, 상근이의 위치가 끝에 닿았을때 true를 주면서 현재의 level을 출력하도록 한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

char ary[1000][1000] = { 0, };
queue<pair<short, short>> loc, fire;

int main()
{
	int w, h, level;
	short f, s, t;
	bool solve;
	cin >> t;
	while(t--) {
		level = 0;
		solve = false;
		//loc = queue<pair<int, int>>();
		//fire = queue<pair<int, int>>();
		while (!loc.empty()) loc.pop();
		while (!fire.empty()) fire.pop();
		scanf("%d%d\n", &w, &h);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				scanf("%c", &ary[i][j]);
				if (ary[i][j] == '@') loc.push({ i,j });
				if (ary[i][j] == '*') fire.push({ i,j });
			}				
			getchar();
		}
		while (!loc.empty()) {
			level++;
			int qsize = fire.size();
			for (int i = 0; i < qsize; i++) {
				f = fire.front().first;
				s = fire.front().second;
				fire.pop();
				if (f < h - 1 && ary[f + 1][s] != '#' && ary[f + 1][s] != '*') {
					ary[f + 1][s] = '*';
					fire.push({ f + 1, s });
				}
				if (f > 0 && ary[f - 1][s] != '#' && ary[f - 1][s] != '*') {
					ary[f - 1][s] = '*';
					fire.push({ f - 1, s });
				}
				if (s < w - 1 && ary[f][s + 1] != '#' && ary[f][s + 1] != '*') {
					ary[f][s + 1] = '*';
					fire.push({ f, s + 1 });
				}
				if (s > 0 && ary[f][s - 1] != '#' && ary[f][s - 1] != '*') {
					ary[f][s - 1] = '*';
					fire.push({ f, s - 1 });
				}
			}
			qsize = loc.size();
			for (int i = 0; i < qsize; i++) {
				f = loc.front().first;
				s = loc.front().second;
				loc.pop();
				if (f == h - 1 || f == 0 || s == w - 1 || s == 0) {
					solve = true;
					break;
				}
				else {
					if (f < h - 1 && ary[f + 1][s] == '.') {
						ary[f + 1][s] = '@';
						loc.push({ f + 1, s });
					}
					if (f > 0 && ary[f - 1][s] == '.') {
						ary[f - 1][s] = '@';
						loc.push({ f - 1, s });
					}
					if (s < w - 1 && ary[f][s + 1] == '.') {
						ary[f][s + 1] = '@';
						loc.push({ f, s + 1 });
					}
					if (s > 0 && ary[f][s - 1] == '.') {
						ary[f][s - 1] = '@';
						loc.push({ f, s - 1 });
					}
				}
			}
			if (solve) break;
		}
		if (solve) printf("%d\n", level);
		else printf("IMPOSSIBLE\n");
	}
	return 0;
}