Bin_S+StudyRoom

• 문제

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

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

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

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

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

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

• 입력

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

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

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

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

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

• 출력

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

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

• 예제 입력

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

• 예제 출력

3

• 접근방식

bfs로 불의 최단거리와 병훈이의 최단거리를 비교해나간다. + 불은 1개 이상 존재함 (1개만 존재하는게 아닐수도 있음), 불이 없는 경우도 존재하기 때문에 높은 수의 변수를 지정해놓음

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;

// 가장 빠른 탈출시간 -> bfs
// 불은 네방향으로 확산
// 불의 최단거리와 병훈이의 최단거리 비교
// ret = person_check[y][x] 부분 C6385오류 발생

const int INF = 987654321;
char a[1004][1004];
int n, m, sx, sy, dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 }, ret, y, x;
int fire_check[1004][1004], person_check[1004][1004];
bool in(int a, int b) 
{
	return 0 <= a && a < n && 0 <= b && b < m;
}

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

	queue<pair<int, int>> q;
	cin >> n >> m;
	fill(&fire_check[0][0], &fire_check[0][0] + 1004 * 1004, INF);
	for (int i = 0; i < n; i++)
    {
		for (int j = 0; j < m; j++)
        {
			cin >> a[i][j];
			if (a[i][j] == 'F')
            {
				fire_check[i][j] = 1; q.push({ i, j });
			}
			else if (a[i][j] == 'J')
            {
				sy = i; sx = j;
			}
		}
	}

	while (q.size()) // 불의 최단거리 먼저 구하기
    {
		tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
        {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!in(ny, nx)) continue;
			if (fire_check[ny][nx] != INF || a[ny][nx] == '#') continue;
			fire_check[ny][nx] = fire_check[y][x] + 1;
			q.push({ ny, nx });
		}
	}

	person_check[sy][sx] = 1;
	q.push({ sy,sx });
	while (q.size())
    {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		if (x == m - 1 || y == n - 1 || x == 0 || y == 0) // 빠져 나오는 부분
        {
			ret = person_check[y][x];
			break;
		}
		for (int i = 0; i < 4; i++)
        {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!in(ny, nx)) continue;
			if (person_check[ny][nx] || a[ny][nx] == '#') continue;
			if (fire_check[ny][nx] <= person_check[y][x] + 1) continue;
			person_check[ny][nx] = person_check[y][x] + 1;
			q.push({ ny, nx });
		}
	}
	if (ret != 0) cout << ret << "\n";
	else cout << "IMPOSSIBLE \n";
	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/4179