불! C++

📝 문제

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

 

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

---

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

---

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

---

입출력

예제 입력

4 4
####
#JF#
#..#
#..#

예제 출력

3

---

첫 번째 시도- 실패

#include<iostream>
#include<queue>
using namespace std;

void BFS(queue<pair<int, int>> q_Ji, queue<pair<int, int>> q_Fire);

char cBoard[1002][1002];
int iDist[1002][1002];
bool bVisitFire[1002][1002];

int dx[4]{ 1, 0, -1, 0 };
int dy[4]{ 0, 1, 0 ,-1 };

int n(0), m(0);

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

	queue<pair<int, int>> q_Ji;
	queue<pair<int, int>> q_Fire;

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> cBoard[i][j];

			if (cBoard[i][j] == 'J')
				q_Ji.push({ i,j });	// 지훈의 시작점을 저장

			if (cBoard[i][j] == 'F')
			{
				q_Fire.push({ i,j });	// 불의 시작점을 저장
				bVisitFire[i][j] = true;
			}

			if (cBoard[i][j] == '.')	// 갈 수 있는 위치면
				iDist[i][j] = -1;	// dist엔 -1로 저장
		}
	}

	BFS(q_Ji, q_Fire);

	return 0;
}

void BFS(queue<pair<int, int>> q_Ji, queue<pair<int, int>> q_Fire)
{
	while (!q_Ji.empty())
	{
		pair<int, int> temp = q_Ji.front();
		q_Ji.pop();

		for (int i = 0; i < 4; ++i)
		{
			int mx = temp.first + dx[i];
			int my = temp.second + dy[i];

			if (mx < 0 || mx >= n || my < 0 || my >= m)
			{
				// 탈출 성공
				int result = iDist[temp.first][temp.second];
				cout << result + 1 << endl;
				return;
			}

			if (cBoard[mx][my] == 'F' || bVisitFire[mx][my] || cBoard[mx][my] != '.')
				continue;

			q_Ji.push({ mx, my });
			iDist[mx][my] = iDist[temp.first][temp.second] + 1;
		}

		pair<int, int> FTemp = q_Fire.front();
		q_Fire.pop();
		for (int i = 0; i < 4; ++i)
		{
			int mx = FTemp.first + dx[i];
			int my = FTemp.second + dy[i];

			if (cBoard[mx][my] == 'F' || bVisitFire[mx][my] || cBoard[mx][my] != '.')
				continue;

			q_Fire.push({ mx, my });
			bVisitFire[mx][my] = true;
		}
	}

	cout << "IMPOSSIBLE";
}

두 번째 시도 - 성공

#include<iostream>
#include<queue>
using namespace std;

void BFS(queue<pair<int, int>> q_Ji, queue<pair<int, int>> q_Fire);

string strBoard[1002];
int iDist[1002][1002];
int iDistFire[1002][1002];

int dx[4]{ 1, 0, -1, 0 };
int dy[4]{ 0, 1, 0 ,-1 };

int n(0), m(0);

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

	queue<pair<int, int>> q_Ji;
	queue<pair<int, int>> q_Fire;

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		fill(iDist[i], iDist[i] + m, -1);
		fill(iDistFire[i], iDistFire[i] + m, -1);
	}

	for (int i = 0; i < n; ++i)
	{
		cin >> strBoard[i];

		for (int j = 0; j < m; ++j)
		{
			if (strBoard[i][j] == 'J')
			{
				q_Ji.push({ i,j });	// 지훈의 시작점을 저장
				iDist[i][j] = 0;
			}

			if (strBoard[i][j] == 'F')
			{
				q_Fire.push({ i,j });	// 불의 시작점을 저장
				iDistFire[i][j] = 0;
			}
		}
	}

	BFS(q_Ji, q_Fire);

	return 0;
}

void BFS(queue<pair<int, int>> q_Ji, queue<pair<int, int>> q_Fire)
{
	// 불 BFS
	while (!q_Fire.empty())
	{
		pair<int, int> FTemp = q_Fire.front();
		q_Fire.pop();
		for (int i = 0; i < 4; ++i)
		{
			int mx = FTemp.first + dx[i];
			int my = FTemp.second + dy[i];

			if (mx < 0 || mx >= n || my < 0 || my >= m)
				continue;

			if (iDistFire[mx][my] >= 0 || strBoard[mx][my] == '#')
				continue;

			iDistFire[mx][my] = iDistFire[FTemp.first][FTemp.second] + 1;
			q_Fire.push({ mx, my });
		}
	}

	// 지훈 BFS
	while (!q_Ji.empty())
	{
		pair<int, int> temp = q_Ji.front();
		q_Ji.pop();

		for (int i = 0; i < 4; ++i)
		{
			int mx = temp.first + dx[i];
			int my = temp.second + dy[i];

			if (mx < 0 || mx >= n || my < 0 || my >= m)
			{
				// 탈출 성공
				int result = iDist[temp.first][temp.second];
				cout << result + 1;
				return;
			}

			if (iDist[mx][my] >= 0 ||  strBoard[mx][my] == '#')
				continue;

			if (iDistFire[mx][my] != -1 && iDistFire[mx][my] <= iDist[temp.first][temp.second] + 1)
				continue;

			iDist[mx][my] = iDist[temp.first][temp.second] + 1;
			q_Ji.push({ mx, my });
		}
	}

	cout << "IMPOSSIBLE";
}

• 이 문제를 해석해보면, 불은 상하좌우로 번지고, 지훈은 상하좌우로 움직이며, 벽으로 막힌 곳을 제외한 길로만 움직일 수 있으며 주어진 맵에서 벗어나면 탈출 성공, 탈출하지 못하면 탈출 실패로 "IMPOSSIBLE"를 출력해주면 된다.

✍️ 중요 포인트

• 첫 번째 시도는 지훈과 불이 한 루프당 같이 움직이며, 지훈이 먼저 움직이고, 불이 먼저 움직이는 형태로 구현해 보았다.
  • 지훈은 불이 지났던 곳도 갈 수 없게 되어서 괜찮은 코드라 생각했지만 실패.
• 두 번째 시도 전 메모리 초과로 실패하였다
  • map을 char 2차원 배열이 아닌 string 1차원 배열로 메모리를 최적화시켜주었다.
• 두 번째 시도는 불과 지훈 모두 BFS를 각각 돌리는 형태이다.
  • 불이 먼저 번지는 속도를 저장하고, 지훈은 그보다 느리거나, 벽이 있으면 못 가는 형태로 구현하였다.