[BOJ 5247] 불

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

5427번: 불

---

위 문제는 여러 테스트 케이스가 주어지고, 맵의 크기도 1000이 되기 때문에 상근이가 이동할 때마다 불을 옮기면 시간초과가 날 수 있다.

 

그래서 맵의 정보를 가지는 배열 A를 만들어 

-1 = 벽

0 = 빈 공간

1 = 불

위 정보를 통해 초기화를 해둔다. 

 

BFS로 불을 옮기면서 배열의 빈 공간을 i+1로 초기화한다. 이는 불이 i + 1초 후에 불이 옮긴다는 것을 의미한다. 

#	#	#	.	#	#	#
#	*	#	.	#	*	#
#	.	.	.	.	.	#
#	.	.	.	.	.	#
#	.	.	@	.	.	#
#	#	#	#	#	#	#

위와 같이 맵이 주어지면, BFS를 통해 각 빈 공간을 불이 붙는 시간으로 설정하면

-1	-1	-1	6	-1	-1	-1
-1	1	-1	5	-1	1	-1
-1	2	3	4	3	2	-1
-1	3	4	5	4	3	-1
-1	4	5	6	5	4	-1
-1	-1	-1	-1	-1	-1	-1

위와 같이 초기화가 된다.

 

맵을 초기화한 후에 상근이의 위치를 기준으로 갈 수 있는 곳을 BFS로 탐색을 하면 된다.

---

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

using namespace std;

int w, h;
int a[1001][1001];
int dst[1001][1001];

int dr[4] = { 0, 0, -1, 1 };
int dc[4] = { 1, -1, 0, 0 };

int solve(int r, int c)
{

	queue<pair<int, int>> q;
	q.push({ r,c });

	dst[r][c] = 1;
	while (!q.empty())
	{
		pair<int, int> p = q.front(); q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nr = p.first + dr[i];
			int nc = p.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= h || nc >= w)
			{
				return dst[p.first][p.second];
			}
			if (dst[nr][nc])
				continue;

			if (a[nr][nc] > dst[p.first][p.second] + 1 || a[nr][nc] == 0)
			{
				dst[nr][nc] = dst[p.first][p.second] + 1;
				q.push({ nr,nc });
			}
		}
	}
	return -1;
}

int main()
{
	int T;
	scanf("%d", &T);

	while (T--)
	{
		queue<pair<int, int>> q;
		pair<int, int> pos;
		scanf("%d%d", &w, &h);
		for (int i = 0; i < h; i++)
		{
			char s[1001];
			scanf("%s", s);
			for (int j = 0; j < w; j++)
			{
				dst[i][j] = 0;
				if (s[j] == '.')
					a[i][j] = 0;
				else if (s[j] == '#')
					a[i][j] = -1;
				else if (s[j] == '*')
				{
					q.push({ i,j });
					a[i][j] = 1;
				}
				else
				{
					a[i][j] = 0;
					pos = { i,j };
				}
			}			
		}

		while (!q.empty())
		{
			pair<int, int> p = q.front(); q.pop();

			for (int i = 0; i < 4; i++)
			{
				int nr = p.first + dr[i];
				int nc = p.second + dc[i];

				if (nr < 0 || nc < 0 || nr >= h || nc >= w)
					continue;

				if (a[nr][nc] == 0)
				{
					a[nr][nc] = a[p.first][p.second] + 1;
					q.push({ nr,nc });
				}
			}
		}

		int ans = solve(pos.first, pos.second);
		if (ans == -1)
			puts("IMPOSSIBLE");
		else
			printf("%d\n", ans);
	}
}