[백준 - 4179] [BFS] 불!

불! 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

22583

5380

3665

21.926%

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

예제 입력 1 복사

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

예제 출력 1 복사

3

---

바킹독 알고리즘 강좌 0x09 BFS 연습문제.

해당 강좌 참고하고 구현함.

풀이 과정

불이 확산되는 과정 -> BFS 이용

지훈이와 불 두개에 대해서 따로 모두 BFS 돌리면 됨.

1. 먼저 불만 BFS 돌린다 => 불이 전파되는 시간(거리) 구함

2. 그 다음 지훈이 BFS 돌려서 이동시킴.

 -> 단, 만약에 지훈이가 x시간에 어떤 칸을 방문했는데 해당 칸이 x시간에 불이 붙었거나 / 이미 그 시간 이전에 불이 붙은 칸이면 이동 불가.

 => 원래 BFS의 구현에서는 큐 안에서 (nx, ny)를 살펴볼때 방문했는지 여부를 vis[nx][ny]가 true인지 혹은 dist[nx][ny]가 0 이상인지 확인하고, 이미 방문한 칸이라면 continue. 이 문제에서는 추가로 해당 칸에 불이 붙은 시간을 확인해서 필요에 따라 continue를 하면 된다.

* 이것도 붙어서 입력받으니까 string 배열 사용.

* 가장자리 까지 가면 탈출 가능 -> 거리에서 +1 해야함

 

 

 

코드

#include <iostream>
#include <queue>

#define X first
#define Y second

using namespace std;

string board[1002]{};
int dist1[1002][1002]{}; // 지훈 이동시간 구하는 dist배열
int dist2[1002][1002]{}; // 불 이동시간 구하는 dist배열

int dx[4] = { 1,0,-1,0 }; //행
int dy[4] = { 0,1,0,-1 }; //열

int main()
{
	queue<pair<int, int>> bfsQ_J; // 지훈 큐
	queue<pair<int, int>> bfsQ_F; // 불 큐

	int R = 0, C = 0;

	cin >> R >> C;

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

	for (int i = 0; i < R; ++i)
	{
		for (int j = 0; j < C; ++j)
		{
			dist1[i][j] = -1;
			dist2[i][j] = -1;
			if (board[i][j] == 'J') // 지훈이 시작점
			{
				dist1[i][j] = 0;
				bfsQ_J.push({ i,j });
			}
			if (board[i][j] == 'F') // 불 시작점
			{
				dist2[i][j] = 0;
				bfsQ_F.push({ i,j });
			}
		}
	}

	while (!bfsQ_F.empty()) // 불에 대한 BFS
	{
		pair<int,int> curPos = bfsQ_F.front();
		bfsQ_F.pop();
		for (int i = 0; i < 4; ++i)
		{
			// curPos의 상하좌우 칸 살펴서
			int nx = curPos.X + dx[i];
			int ny = curPos.Y + dy[i];
			if (nx < 0 || ny < 0 || nx >= R || ny >= C)
				continue;
			if (board[nx][ny] == '#' || dist2[nx][ny] >= 0) // 못 지나가는 칸이거나 이미 방문한 칸이라면
				continue;
			dist2[nx][ny] = dist2[curPos.X][curPos.Y] + 1; // 상하좌우 각 칸이 갈수 있는 곳일 때 현재칸보다 거리 1씩 증가
			bfsQ_F.push({ nx,ny });
		}
	}

	while (!bfsQ_J.empty()) // 지훈이에 대한 BFS
	{
		auto curPos = bfsQ_J.front();
		bfsQ_J.pop();
		for (int i = 0; i < 4; ++i)
		{
			int nx = curPos.X + dx[i];
			int ny = curPos.Y + dy[i];
			if (nx < 0 || ny < 0 || nx >= R || ny >= C) // 범위를 벗어났다는 것은 탈출에 성공했다는 것.
			{
				printf("%d", dist1[curPos.X][curPos.Y] + 1); // 현재 위치에서 탈출 가능함
				return 0;
			}
			if(board[nx][ny] == '#' || dist1[nx][ny] >= 0)// 못 지나가는 칸이거나 이미 방문한 칸이라면
				continue;
			if (dist2[nx][ny] != -1 && dist2[nx][ny] <= dist1[curPos.X][curPos.Y]+1/*방문할 시간이니까 +1*/) // 지훈이가 방문할 칸이 불이 확산되는 칸인데 지훈이가 방문할 시간보다 빠르다면
				continue;
			dist1[nx][ny] = dist1[curPos.X][curPos.Y] + 1;
			bfsQ_J.push({ nx,ny });
		}
	}
	// while문 빠져 나왔으면 탈출 실패한거임.
	printf("IMPOSSIBLE");
}

 

 

알게된 것

이 문제는 시작점이 두 종류인 문제.

이 문제는 지훈이의 이동은 불의 전파에 영향을 받지만 불의 전파는 지훈이의 이동에 영향을 받지 않아서 불만 먼저 전파를 쭉 시키는게 가능했다.

그런데 시작점이 두 종류인 문제에 관해서 추가로 생각해야 할점

-> 전파에 서로 상호작용이 있다면 :

예를 들어 시작점이 A, B 두 종류가 있고, A의 전파에 B가 영향을 주고 B의 전파에도 A가 영향을 준다고 해보자.

지금 이 문제에서 불과 지훈이가 아니라 불과 소방수 내지는 불과 물이 전파되는 문제여서 둘이 만나면 뭔가 상호작용이 발생한다고 생각을 하면 어느 하나를 먼저 끝까지 전파시키는게 불가능.