[백준/BOJ] 백준 5427번 : 불

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

5427번: 불

불의 확산을 표현하는 함수를 만들었고, start지점에서 출구로 탈출하는데 가장 빠른 시간을 구하는 함수를 만들었다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
#include <string>
using namespace std;

int w, h;
vector<string> board;
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int discoverd[1000][1000];
int depth[1000][1000];
queue<pair<int, int>> fire;

//불이 인접한 칸으로 확산된다. 확산으로 생성된 불들은 지금 확산되지 않고 나중에 확산될때 사용되므로 큐에 저장해놓는다
//확산된 불들은 이제 의미가 없으므로 큐에서 pop한다
void fireSpread()
{
	int fire_size = fire.size();

	for (int i = 0; i < fire_size; i++)
	{
		pair<int, int> this_fire = fire.front();
		fire.pop();

		for (int j = 0; j < 4; j++)
		{
			pair<int, int> there_fire = make_pair(this_fire.first + dx_dy[j][0], this_fire.second + dx_dy[j][1]);

			if (there_fire.first >= 0 && there_fire.first < h && there_fire.second >= 0 && there_fire.second < w && board[there_fire.first][there_fire.second] == '.')
			{
				board[there_fire.first][there_fire.second] = '*';
				fire.push(there_fire);
			}
		}
	}
}

int Solve(pair<int, int> start)
{
	discoverd[start.first][start.second] = 1;
	depth[start.first][start.second] = 0;

	queue<pair<int, int>> q;
	q.push(start);

	int q_size;

	while (!q.empty())
	{
		q_size = q.size();

		//불이 확산된다
		fireSpread();

		for (int i = 0; i < q_size; i++)
		{
			pair<int, int> here = q.front();
			q.pop();

			//가장자리에 도달했을때
			if (here.first == h - 1 || here.second == w - 1 || here.first == 0 || here.second == 0)
				return depth[here.first][here.second] + 1;

			for (int i = 0; i < 4; i++)
			{
				pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
				if (there.first >= 0 && there.first < h && there.second >= 0 && there.second < w && board[there.first][there.second] != '#' && board[there.first][there.second] != '*' && discoverd[there.first][there.second] == 0)
				{
					discoverd[there.first][there.second] = 1;
					depth[there.first][there.second] = depth[here.first][here.second] + 1;

					q.push(there);
				}
			}
		}
	}

	return -1;
}

void Pre()
{
	memset(discoverd, 0, sizeof(discoverd));
	memset(depth, 0, sizeof(depth));
	board.clear();

	while (!fire.empty())
		fire.pop();
}

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

	int testcase;
	string temp;
	pair<int, int> start;
	int result;

	cin >> testcase;

	for (int t = 0; t < testcase; t++)
	{
		//초기화
		Pre();

		cin >> w >> h;

		for (int i = 0; i < h; i++)
		{
			cin >> temp;
			board.push_back(temp);

			for (int j = 0; j < w; j++)
			{
				//시작위치를 저장하고 표시는 빈공간과 같이 '.'로 바꾼다
				if (board[i][j] == '@')
				{
					start = make_pair(i, j);
					board[i][j] = '.';
				}

				//불의 위치들은 저장한다
				else if (board[i][j] == '*')
					fire.push(make_pair(i, j));
			}
		}

		result = Solve(start);

		if (result == -1)
			cout << "IMPOSSIBLE" << "\n";
		else
			cout << result << "\n";

	}

	return 0;
}