[백준 BOJ5427] 불 (C++)

 

1. 제목

- 백준 5427 불

- BOJ 5427불

문제 링크 : 5427번: 불 (acmicpc.net)

5427번: 불

 

---

2. 문제 설명

불 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	28527	7331	4316	46.933%

문제

 

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1 복사

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1 복사

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번

• 문제의 오타를 찾은 사람: adh0463
• 데이터를 추가한 사람: b8goal, djm03178
• 문제를 번역한 사람: baekjoon

알고리즘 분류

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

 

---

3. 풀이 과정

BOJ 3055랑 아주 유사한 문제였어요. 풀이 과정이 완전 똑같았어요. 한 턴마다 불과 상근이가 이동해야 하고 불이 먼저 번져 나간 이후에 상근이가 이동해야 문제에서 요구하는 조건인 불이 붙으려는 칸으로 이동할 수 없다를 만족하게 돼요. 그래서 이문제도 q를 2개 구현했고 각각 탐색을 하기 전 미리 q에 들어가 있는 좌표의 개수를 구해놓은 다음 해당 턴에는 탐색을 시작 하기 전 들어 있는 좌표만 탐색하게 진행하게 했어요.

이 문제는 도착 좌표가 따로 정해져 있지 않고 맵을 벗어나게 되면 탈출이라는 규칙을 갖고 있었기에 탐색 범위가 맵을 벗어났을 때 탈출했다는 조건을 줘야 해요.

0초

1초

2초

이제 다음 탐색에 상근이 위치로 불이 번질 텐데 상근이는 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다는 규칙이 있기에 이 순간부터 불은 상근이를 잡을 수가 없어요. 그래서 불은 더 이상 탐색하지 않아요.

 

3초

4초

5초(탈출 성공)

 

---

4. 함수 설명

MoveFire : 불이 번져 나가는 것을 구현해주는 함수예요.

MoveS : 상근이가 이동하는 함수예요. 탐색 전 MoveFire 를 호출하여 불이 먼저 움직인 다음 상근이가 움직이게 했어요.

---

5. 코드

#define MAX 1000 + 1
#define X second
#define Y first
#include <iostream>
#include <queue>

using namespace std;

// 상하좌우
int dx[4] = { 0, 0,-1, 1 };
int dy[4] = { 1, -1, 0, 0 };

char map[MAX][MAX];
int w, h;

queue < pair<int, int>> sq;
queue < pair<int, int>> fq;

void MoveFire()
{
	int cnt = fq.size();
	for (int i = 0; i < cnt; i++)
	{
		pair<int, int> cur = fq.front();
		fq.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (ny < 0 || nx < 0 || ny >= h || nx >= w)
				continue;
			if (map[ny][nx] != '.')
				continue;

			map[ny][nx] = '*';
			fq.push({ ny, nx });
		}
	}
}

int MoveS()
{
	int time = 0;
	while (!sq.empty())
	{
		time++;
		MoveFire();

		int cnt = sq.size();
		for (int i = 0; i < cnt; i++)
		{
			pair<int, int> cur = sq.front();
			sq.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];

				if (ny < 0 || nx < 0 || ny >= h || nx >= w)
					return time;

				if (map[ny][nx] != '.')
					continue;

				map[ny][nx] = '@';
				sq.push({ ny, nx });
			}
		}
	}

	return -1;
}

void Reset(int w, int h)
{
	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			map[y][x] = '.';
		}
	}
	while (!sq.empty())
		sq.pop();
	while (!fq.empty())
		fq.pop();
}

int main()
{
	int t;
	cin >> t;	

	for (int i = 0; i < t; i++)
	{
		cin >> w >> h;
		for (int y = 0; y < h; y++)
		{
			for (int x = 0; x < w; x++)
			{
				cin >> map[y][x];

				if (map[y][x] == '@')
					sq.push({ y, x });
				else if (map[y][x] == '*')
					fq.push({ y, x });
			}
		}
		int time = MoveS();
		if (time == -1)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << time << endl;

		Reset(w, h);
	}

	return 0;
}