백준 5427 - 불

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 불이 번지는 빌딩에서 얼마나 빨리 상근이가 탈출할 수 있는지 구하는 문제이다.

이때, 불은 상하좌우로 한 칸씩 번지며 상근이 역시 한 칸씩 이동할 수 있다.

 

문제를 보면 bfs나 dfs로 접근해야 한다는 것은 쉽게 알 수 있다.

하지만, 이 문제의 핵심은 bfs를 두 개 진행해야 한다는 점이다.

불이 번지는 것과 상근이가 이동하는 경우의 수 총 두 개다.

 

또한, 불이 번지는 과정에서 상근이가 이동해야 하기 때문에 빌딩의 모습을 유지해야 한다.

즉, 불이 한 번 번지고 상근이가 이동하고 또다시 불이 번지고 상근이가 이동하는 것을 반복하면 된다.

 

불이 번지는 것을 단계별로 진행해야 하기 때문에 큐의 사이즈를 초기에 저장한 뒤 그만큼만 pop 하여 bfs를 진행하면 단계별로 진행할 수 있다.

불이 번지는 것을 모두 구현했다면 상근이가 이동할 수 있는 경우의 수를 bfs로 구하면 된다.

int cnt = 0;
bool flag = false;
while (!q.empty())
{
	int size = q.size();

	for (int t = 0; t < size; t++)
	{
		auto [y, x] = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int newY = y + dy[i];
			int newX = x + dx[i];

			if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
			if (board[newY][newX] == '*' || board[newY][newX] == '#') continue;

			board[newY][newX] = '*';
			q.push({ newY, newX });
		}
	}

	int playerSize = player.size();

	for(int p = 0 ; p < playerSize; p++)
	{
		auto [y, x] = player.front();
		player.pop();

		for (int i = 0; i < 4; i++)
		{
			int newY = y + dy[i];
			int newX = x + dx[i];

			if (newY < 0 || newY >= N || newX < 0 || newX >= M)
			{
				//탈출
				cout << cnt + 1 << "\n";
				flag = true;
				break;
			}
			if (board[newY][newX] == '*' || board[newY][newX] == '#') continue;
			if (visited[newY][newX]) continue;
			visited[newY][newX] = true;

			player.push({ newY, newX });
		}

		if (flag) break;
	}

	if (flag) break;
	cnt++;
}

 

여기서 주의할 점이 있다.

입력 중 불이 끝까지 번지지 못하거나 아예 없는 경우가 존재한다.

이런 경우에는 상근이가 탈출하기 전에 불을 관리하는 큐가 비어버려 올바른 답을 구하지 못하게 된다.

따라서, 마지막에 현재까지 관리된 상근이의 위치를 탈출할 때까지 bfs로 진행해 줘야 한다.

void Move(int cnt)
{
	while (!player.empty())
	{
		int size = player.size();

		for (int p = 0; p < size; p++)
		{
			auto [y, x] = player.front();
			player.pop();

			for (int i = 0; i < 4; i++)
			{
				int newY = y + dy[i];
				int newX = x + dx[i];

				if (newY < 0 || newY >= N || newX < 0 || newX >= M)
				{
					cout << cnt + 1 << "\n";
					return;
				}
				if (board[newY][newX] == '*' || board[newY][newX] == '#') continue;
				if (visited[newY][newX]) continue;
				visited[newY][newX] = true;

				player.push({ newY, newX });
			}
		}

		cnt++;
	}

	cout << "IMPOSSIBLE\n";
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T, N, M;
vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };

vector<vector<char>> board;
vector<vector<bool>> visited;
queue<pair<int, int>> player;

void Move(int cnt)
{
	while (!player.empty())
	{
		int size = player.size();

		for (int p = 0; p < size; p++)
		{
			auto [y, x] = player.front();
			player.pop();

			for (int i = 0; i < 4; i++)
			{
				int newY = y + dy[i];
				int newX = x + dx[i];

				if (newY < 0 || newY >= N || newX < 0 || newX >= M)
				{
					cout << cnt + 1 << "\n";
					return;
				}
				if (board[newY][newX] == '*' || board[newY][newX] == '#') continue;
				if (visited[newY][newX]) continue;
				visited[newY][newX] = true;

				player.push({ newY, newX });
			}
		}

		cnt++;
	}

	cout << "IMPOSSIBLE\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> T;

	while (T--)
	{
		cin >> M >> N;

		board.clear();
		visited.clear();
		while (!player.empty()) player.pop();

		board.resize(N, vector<char>(M));
		visited.resize(N, vector<bool>(M, false));

		pair<int, int> pos;
		queue<pair<int, int>> q;

		for (int i = 0; i < N; i++)
		{
			string str;
			cin >> str;
			for (int j = 0; j < M; j++)
			{
				board[i][j] = str[j];
				if (board[i][j] == '@')
				{
					pos = { i, j };
				}
				if (board[i][j] == '*')
				{
					q.push({ i,j });
				}
			}
		}
		
		player.push(pos);
		visited[pos.first][pos.second] = true;

		int cnt = 0;
		bool flag = false;
		while (!q.empty())
		{
			int size = q.size();

			for (int t = 0; t < size; t++)
			{
				auto [y, x] = q.front();
				q.pop();

				for (int i = 0; i < 4; i++)
				{
					int newY = y + dy[i];
					int newX = x + dx[i];

					if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
					if (board[newY][newX] == '*' || board[newY][newX] == '#') continue;

					board[newY][newX] = '*';
					q.push({ newY, newX });
				}
			}

			int playerSize = player.size();

			for(int p = 0 ; p < playerSize; p++)
			{
				auto [y, x] = player.front();
				player.pop();

				for (int i = 0; i < 4; i++)
				{
					int newY = y + dy[i];
					int newX = x + dx[i];

					if (newY < 0 || newY >= N || newX < 0 || newX >= M)
					{
						//탈출
						cout << cnt + 1 << "\n";
						flag = true;
						break;
					}
					if (board[newY][newX] == '*' || board[newY][newX] == '#') continue;
					if (visited[newY][newX]) continue;
					visited[newY][newX] = true;

					player.push({ newY, newX });
				}

				if (flag) break;
			}

			if (flag) break;
			cnt++;
		}

		if(!flag) Move(cnt);
	}

	return 0;
}

---