백준 Gold 3 불!

불! (백준 Gold 3)

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

미로에서 불이 났을때 탈출할 수 있는지
탈출 가능하다면 그 최단 시간을 구하는 문제

• 사람과 불은 상하좌우로 이동 가능 (시간당 1칸)
  (다만 벽을 통과할 순 없음)
  
• 사람은 1명만 주어지며, 불보다 먼저 이동
  
• 가장 끝 칸에서, 한번 더 움직여야 탈출 가능
  
• 불은 매시간마다 상하좌우로 ‘확산’
  

풀이 방법

BFS 문제

• 각 시간을 ‘지정’해야 하기에
  큐에 집어넣는 순서를 까다롭게 지정해야 함
  플레이어 -> 4방향 검사 후 Push
  불 -> 4방향 검사 후 Push
  이 순서대로 진행시, 플레이어가 불보다 먼저 움직일 수 있음
  (또한 다시 플레이어로 넘어온 시점이 곧 1 시간의 증가)
  

• 플레이어가 ‘끝’칸에 도달하더라도 그 칸이 이미
  ‘불’이 붙어 있다면 실패이므로
  ‘도착 시점’에서 한번 더 검사
  (끝칸에서 바로 탈출하면 불이 그것을 막는 경우의 수를 놓침)
  

제출 코드

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

using namespace std;

const int dirY[4] = { 0,-1,0,1 };
const int dirX[4] = { -1,0,1,0 };

int r,c;

struct infos
{
	int y, x;
	int cost;
	bool bPlayer;
};

int bfs(vector<string>& maps,const pair<int,int>& start,const vector<pair<int,int>> fires)
{
	vector<vector<bool>> visit(r, vector<bool>(c, false));
	queue<infos> pq;
	pq.push({ start.first,start.second,0,true });

	for (const auto& f : fires)
	{
		pq.push({ f.first,f.second,-1,false });
	}

	while (pq.empty() == false)
	{
		int nowy = pq.front().y;
		int nowx = pq.front().x;
		int nowcost = pq.front().cost;
		bool isPlayer = pq.front().bPlayer;
		pq.pop();

		if (isPlayer)
		{
			if (nowy < 0 ||
				nowy > r - 1 ||
				nowx < 0 ||
				nowx > c - 1)
			{
				return nowcost;
			}

			if (maps[nowy][nowx] == 'F')
				continue;

			for (int i = 0; i < 4; i++)
			{
				int ny = nowy + dirY[i];
				int nx = nowx + dirX[i];

				if (ny < 0 || ny >= r ||
					nx < 0 || nx >= c)
				{
					pq.push({ ny,nx,nowcost + 1,true }); // 탈출 조건
					continue;
				}

				if (maps[ny][nx] == '#' || maps[ny][nx] == 'F')
					continue;
				
				if (visit[ny][nx])
					continue;

				visit[ny][nx] = true;
				pq.push({ ny,nx,nowcost + 1,true });
			}
		}
		else
		{
			for (int i = 0; i < 4; i++)
			{
				int ny = nowy + dirY[i];
				int nx = nowx + dirX[i];

				if (ny < 0 || ny >= r ||
					nx < 0 || nx >= c)
					continue;

				if (maps[ny][nx] == '#' || maps[ny][nx] == 'F')
					continue;

				maps[ny][nx] = 'F';
				pq.push({ ny,nx,nowcost + 1,false });
			}
		}

	}

	return -1;
}

int main()
{
	cin >> r >> c;

	vector<string> maps(r);

	pair<int, int> start;
	vector<pair<int, int>> fires;

	for (int i = 0; i < r; i++)
	{
		cin >> maps[i];
		for (int j = 0; j < c; j++)
		{
			if (maps[i][j] == 'J')
			{
				start.first = i;
				start.second = j;
			}
			else if (maps[i][j] == 'F')
			{
				fires.push_back({ i,j });
			}
		}
	}

	int v = bfs(maps, start, fires);
	if (v == -1)
		cout << "IMPOSSIBLE";
	else
		cout << v;

	return 0;
}

결과

BFS 중에서 ‘다른 동적 요소’를 집어넣고
같이 BFS를 돌리는 재미있는 문제였다

• 원래는 더 높은 난이도의 문제에 도전해보려 하였으나
  현재는 Gold의 문제들을 푸는데 먼저 익숙해질 필요가 있어보인다
  (골드 난이도 1,2를 1시간 내로 풀 정도)