[백준] C++ 불!(4179)

너비우선탐색 문제이다. 생각보다 고려해야 할 경우의 수가 많아서 헷갈렸다.

 

1. 지훈이는 이미 이동한 경로로 다시 이동하지 못한다.

2. 지훈이는 이전에 불이 난 장소로는 이동하지 못한다.

3. 이미 불이 난 곳은 다시 탐색하지 않는다.

4. 사람이 모서리에 도착하면 탈출할 수 있다고 판단함.

5. 사람이 출발하기 전에 출발하려는 장소가 불이 났는지 안 났는지 판단해야 함.

 

사람이 출발하기 전에 출발하려는 장소가 불이 났는지 안 났는지 판단해야하는 이유.

이렇게 주어졌을 때

사람이 먼저 이동 한 후

불이 이동을 하게 되면 불과 사람이 겹친다.

그렇기 때문에 사람은 출발하기 전 자신의 위치에 불이 났는지 확인하는 작업이 필요하다.

 

#include <iostream>
#include <queue>;

using namespace std;

char arr[1001][1001];
int visited[1001][1001];
int visited2[1001][1001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
priority_queue<pair<pair<int, char>, pair<int, int>>>q;
void BFS();


int R = 0;
int C = 0;
int main(void)
{


	cin >> R >> C;

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 'J')
			{
				q.push({ {0,'J'},{i, j} });
			}
			if (arr[i][j] == 'F')
			{
				q.push({ {0,'F'},{i, j} });
			}
		}
	}

	BFS();

	return 0;
}

void BFS()
{
	int sig = 0;
	int result = 0;
	while (!q.empty())
	{
		int count = -q.top().first.first;
		char c = q.top().first.second;

		int x = q.top().second.first;
		int y = q.top().second.second;
		q.pop();
		if (c == 'J' && visited[x][y] != 0)//만약 확인했는데 불이 나있으면 불타죽은걸로 판정.
		{
			continue;
		}
		if (c == 'F')
		{
			visited[x][y] = 1;
		}

		for (int i = 0; i < 4; i++)
		{
			if (c == 'J')
			{
				if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < R && +dy[i] < C && visited[x + dx[i]][y + dy[i]] == 0 && visited2[x + dx[i]][y + dy[i]] == 0 && arr[x + dx[i]][y + dy[i]] == '.')//불이 난 장소인가?? 이미 방문한 적이 있는가?(사람)
				{
					visited2[x + dx[i]][y + dy[i]] = 1;
					q.push({ {-(count + 1),'J'},{x + dx[i],y + dy[i]} });

				}
				if ((x + dx[i] == -1 || y + dy[i] == -1 || x + dx[i] == R || y + dy[i] == C) && visited[x + dx[i]][y + dy[i]] == 0)//모서리에 도착함.(사람)
				{
					sig = 1;
					result = count + 1;
				}
			}
			else if(c=='F')
			{
				if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < R && y + dy[i] < C && c == 'F' && visited[x + dx[i]][y + dy[i]] == 0 && arr[x + dx[i]][y + dy[i]] != '#' && arr[x + dx[i]][y + dy[i]] != 'F')//이미 방문한적이 있는가??(불)
				{
					visited[x + dx[i]][y + dy[i]] = 1;
					q.push({ {-(count + 1),'F'},{x + dx[i],y + dy[i]} });
				}
			}
		}
		if (sig == 1)
		{
			break;
		}
	}
	if (sig == 0)
	{
		cout << "IMPOSSIBLE";
	}
	else
	{
		cout << result;
	}
}