[알고리즘] C++ 백준 5427 불

 

백준 5427

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

5427번: 불

 

풀이 전 나의 생각

이 문제의 정답률이 굉장히 낮은 이유는 조건을 설정하는 과정에 있어서 정확한

판단을 할 수가 없기 때문이라고 생각한다.

 

우선 차근차근 문제를 알아보자.

 

문제의 요약은 사람이 불에 닿기 전에 탈출을 할 수 있냐 없냐다.

이를 판단하기 위해선 불과 사람이 동시에 움직이는 조건으로 진행해야 한다.

그러면 동시에 진행하는 것 처럼 코드를 제작하여 풀면 되는 것이다. 그 방법으로는 먼저 빈 공간에 몇 분에 불이 붙는지 

구해주어야 한다. 우리가 익히 잘 알고있는 BFS를 이용하여 불이 빈 공간을 탐색하게 만들면 된다.

그러면 불이 언제 붙는지 시간을 표현한 공간이 완성될 것이다. 이 공간을 사람이 탐색하게 만들면 불과 사람이 동시에 움직이는 결과를 낼 수 있다. 예를 들어 빈 공간이 2분 후 불이 붙을 예정인 공간이라고 가정하면 현재 사람이 그 공간에 2초보다 빨리 도달할 수 있다면 불을 피해서 갈 수 있다는 것이고 2초와 같거나 더 큰 시간이 걸린다면 불에 휩싸여서 가지 못하는 공간이 될 것이다. 이러한 조건을 걸고 반복을 하다보면 불에 붙지 않고 탈출할 수 잇는 빈 공간을 탐색할 수 있어 답을 구해 낼 수 있다.

 

요약하자면

 

1. 불이 언제 붙는지 시간을 표현할 공간을 만든 후 BFS 탐색을 진행하여 시간 값을 위치마다 저장해준다.

2. 사람의 움직임을 표현할 공간을 만든 후 1번에서 만든 공간의 시간 값과 비교하며 탐색을 진행한다.

3. 사람이 경계값 밖으로 나갔다면 빌딩을 탈출한 것이니 현재 사람의 위치 값에서 + 1분을 해주어 결과를 출력해주고
모든 위치를 탐색했음에도 경계값 밖으로 나가지 못했다면 "IMPOSSIBLE"을 출력해준다.

4. 테스트 케이스만큼 반복해준다.

 

마지막으로 주의할 점은 큐를 전역변수로 설정했다면 BFS 진행 도중 경계 값을 만나 큐의 값이 모두 pop되지 않고 빠져나갈 수 있기 때문에 테스트 케이스가 끝날 때마다 큐를 초기화 해줘야 한다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
string board[1002];
int fDist[1002][1002];
int jDist[1002][1002];

queue<pair<int, int>> fQ;
queue<pair<int, int>> jQ;
int w, h = 0;

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

		for (int i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];

			if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
			if (fDist[nx][ny] >= 0 || board[nx][ny] == '#') continue;

			fDist[nx][ny] = fDist[p.first][p.second] + 1;
			fQ.push({nx, ny});
		}
	}
}

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

		for (int i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];

			if (nx < 0 || ny < 0 || nx >= h || ny >= w)
			{
				cout << jDist[p.first][p.second] + 1 << '\n';
				return;
			}

			if (board[nx][ny] == '#' || jDist[nx][ny] >= 0) continue;
			if (fDist[nx][ny] != -1 && fDist[nx][ny] <= jDist[p.first][p.second] + 1) continue;

			jDist[nx][ny] = jDist[p.first][p.second] + 1;
			jQ.push({nx, ny});
		}
	}

	cout << "IMPOSSIBLE" << '\n';
}

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

	int t = 0;

	cin >> t;

	while (t--)
	{
		cin >> w >> h;

		for (int i = 0; i < h; i++)
		{
			fill(fDist[i], fDist[i] + w, -1);
			fill(jDist[i], jDist[i] + w, -1);
		}

		for (int i = 0; i < h; i++)
		{
			cin >> board[i];
		}

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (board[i][j] == '*')
				{
					fQ.push({ i, j });
					fDist[i][j] = 0;
				}
				else if (board[i][j] == '@')
				{
					jQ.push({ i, j });
					jDist[i][j] = 0;
				}
			}
		}

		FBFS();
		JBFS();

		while (!jQ.empty()) jQ.pop();
		while (!fQ.empty()) fQ.pop();
	}
}