BaekJoon 5427 불

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

소스결과 4880 KB / 48 ms

언어 C++ 17

분류 BFS

 

설명

불이난 건물에서 상근이가 탈출 하려고한다. 상근이가 얼마만에 탈출 할 수 있는지 알아보자

 

일단 탈출 할 수없는 경우가 존재하기 때문에 경건한 마음으로 문제를 풀어보자..

불과 상근이의 이동중 먼저 BFS를 사용해야 하는 부분은 불이다. 불이 먼저 번진 것으로 가정해야 문제의 조건과 일치한다.

시간의 개념이 있기 때문에 다음에 번질 위치를 기억하는 Queue를 사용한다. 문제에서는 불과 상근이 두번이 필요하기 때문에 Queue는 총 4개 사용한다.

불이 먼저 번진 경우를 board에 기록하면서 BFS를 진행한다. 상근이를 board에 기록해도 되지만 순서가 불이 먼저기에 상근이는 board에 기록하지 않는다. 대신 현재 위치를 방문 했는지를 기억하는 check 배열을 사용한다.

준비는 끝났다 구현해보자.

 

알고리즘

1. 현재 맵 정보를 받아 오면서 불의 위치와 상근이의 위치를 각각의 Queue에 넣는다.

2. 불과 상근이의 이동을 기록하는 BFS를 진행한다. 종료조건은 상근이의 위치를 기록하는 Queue가 비거나 상근이가 탈출하면 종료한다.

 2 - 1. 불이 먼저 번지는 BFS를 진행한다. 불이 번질 위치는 불이 번진것으로 간주해 board에 *로 표시한다.

 2 - 2. 상근이가 이동하는 BFS를 진행한다. 다음 위치가 범위를 벗어나는 경우를 먼저 확인한다. 범위를 벗어나면 Queue에 넣는다.

 2 - 3. 다음 위치가 범위를 벗어나지 않는 경우 다음 위치가 벽, 불이거나 방문한 경우를 제외하고 Queue에 넣는다.

3. BFS를 통해 탈출 했는지, 탈출하지 못했는지를 구분해 출력한다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 1000;

const short posX[4] = { 0, 1, 0, -1 };
const short posY[4] = { 1, 0, -1, 0 };

struct Point {
	short x;
	short y;

	Point() : x(0), y(0) {};
	Point(short x, short y) : x(x), y(y) {};
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int tcc;
	cin >> tcc;

	for (int i = 0; i < tcc; i++)
	{
		queue<Point> fire;
		queue<Point> nextFire;
		queue<Point> sangGeun;
		queue<Point> nextSangGeun;
		int result = 0;
		bool success = false;
		char board[MAX+1][MAX + 1] = {};
		bool check[MAX+1][MAX] = {};
		int row, col;
		cin >> row >> col;

		for (int i = 0; i < col; i++)
		{
			cin >> board[i];
			for (int j = 0; j < row; j++)
				if (board[i][j] == '*')
					fire.push(Point(i, j));
				else if (board[i][j] == '@')
				{
					sangGeun.push(Point(i, j));
					check[i][j] = true;
				}
					
		}

		while (!sangGeun.empty())
		{
			while (!fire.empty())
			{
				Point cur = fire.front();
				fire.pop();

				for (int i = 0; i < 4; i++)
				{
					short nextX = cur.x + posX[i];
					short nextY = cur.y + posY[i];

					if (0 <= nextX && nextX < col && 0 <= nextY && nextY < row && board[nextX][nextY] != '#' && board[nextX][nextY] != '*')
					{
						board[nextX][nextY] = '*';
						nextFire.push(Point(nextX, nextY));
					}
				}
			}

			while (!sangGeun.empty())
			{
				Point cur = sangGeun.front();
				sangGeun.pop();

				if (cur.x == -1 || cur.y == -1 || cur.x == col || cur.y == row)
				{
					success = true;
					break;
				}

				// cout << cur.x << ' ' << cur.y << '\n'; // For Debug

				for (int i = 0; i < 4; i++)
				{
					short nextX = cur.x + posX[i];
					short nextY = cur.y + posY[i];

					if (nextX == -1 || nextY == -1 || nextX == col || nextY == row)
						nextSangGeun.push(Point(nextX, nextY));
					else if (nextX < col && nextY < row && !check[nextX][nextY] &&board[nextX][nextY] != '#' && board[nextX][nextY] != '*')
					{
						check[nextX][nextY] = true;
						nextSangGeun.push(Point(nextX, nextY));
					}
				}
			}

			if (!success)
			{
				while (!nextFire.empty())
				{
					fire.push(nextFire.front());
					nextFire.pop();
				}

				while (!nextSangGeun.empty())
				{
					sangGeun.push(nextSangGeun.front());
					nextSangGeun.pop();
				}
				result++;
			}
			else
				break;
		}

		if (success)
			cout << result << '\n';
		else
			cout << "IMPOSSIBLE\n";
	}

	return 0;
}