[백준] 불! (4179번)

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

예제 입력 1 복사

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

예제 출력 1 복사

3

---

불에 타지 않게 지훈이를 탈출시켜야 하는 문제이다.

흔한 bfs 문제이고 어렵지 않게 풀 수 있다.

요점은 큐에 불과 지훈이를 넣고 불을 먼저 한 칸씩 번지게 한 후 지훈이를 이동시키는 것이다.

불이 한 칸만 있는 줄 알고 풀었다가 틀렸는데, 불은 지도에 여러곳에 있을 수 있다. 따라서 입력을 받을 때 큐를 전역 변수로 선언한 후, 불일때만 큐에 집어넣고, 입력이 모두 끝난 후에 지훈이를 큐에 넣어야한다.

 

bfs를 돌리면서 다음 지점에 갈 수 있을때 이동하고 거리도 늘려준다. 지훈이가 맵의 외곽에 도달하면 이동 거리를 저장하고 끝내면 된다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/bc5ad0f5beec5b1fe7fdc07f746595526b8d7c41/BaekJoon/2020/%EB%B6%88!%20(4197%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;
int N, M, res = 987654321;
int p[1001][1001]; // 0 : 지나갈 수 있음, 1 : 벽 또는 불
int visit[1001][1001];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
int jx, jy;
queue<pair<int, int>> q;

void bfs() {
	q.push({ jx,jy });
	visit[jx][jy] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (p[x][y] == 0 && (x == 1 || x == N || y == 1 || y == M)) {
			res = visit[x][y];
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<1 || ny < 1 || nx>N || ny>M) continue;
			if (p[nx][ny] == 1) continue;
			if (visit[nx][ny] == -1) {
				visit[nx][ny] = visit[x][y] + 1;
				p[nx][ny] = p[x][y];
				q.push({ nx,ny });
			}
		}
	}
}

int main()
{
	cin >> N >> M;
	memset(visit, -1, sizeof(visit));

	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		for (int j = 1; j <= M; j++) {
			if (str[j - 1] == '#')
				p[i][j] = 1;
			else if (str[j - 1] == 'F') {
				p[i][j] = 1;
				q.push({ i,j });
				visit[i][j] = 0;
			}
			else if (str[j - 1] == 'J') {
				p[i][j] = 0;
				jx = i, jy = j;
			}
			else
				p[i][j] = 0;
		}
	}

	bfs();

	if (res == 987654321)
		cout << "IMPOSSIBLE";
	else
		cout << res;
}