[백준] 4179번 불!

4179 불!

문제

---

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

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

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

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

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

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

입력

---

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

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

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

#: 벽

.: 지나갈 수 있는 공간

J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)

F: 불이난 공간

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

출력

---

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

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

---

풀이)

처음에 문제를 제대로 안읽었다가 틀린 문제다.

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

즉, 미로의 경계부분에 지훈이가 도달했을 때를 탈출할 수 있을 때라고 보는 것이다.

(미로 밖으로 나가야 탈출이 되는 줄..)

풀이는 2개의 queue를 이용해서 풀었다.

queue <pair<int,int>> fire; //불의 위치를 저장하는 queue

queue <pair<int,int>> person; //지훈이의 위치를 저장하는 queue

1. fire queue에 저장되어있는 불을 먼저 이동시킴.

2. person queue에 저장되어있는 지훈이를 이동시킴. 

   (지훈이가 이미 방문했던 곳은 방문처리로 표시해놔야 무한루프에 걸리지 않는다.)

  2.1 지훈이가 맵의 가장자리에 도달할 수 있으면 그 때가 탈출 가능한 시점.

  2.2 지훈이가 아직 탈출하지 않았는데, 지훈이 위치를 저장하는 queue가 비었다면 탈출이 불가능 하다는 것.

주의사항

처음 탈출 시간은 1부터 시작한다.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int r, c;
char map[1000][1000];
queue <pair<int, int>> person;//지훈이의 위치
queue <pair<int, int>> fire;//불의 위치
bool visited[1000][1000];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int main() {
    scanf("%d %d", &r, &c);
    getchar();
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            map[i][j] = getchar();
            if (map[i][j] == 'J') {
                map[i][j] = '.';
                person.push({ i,j });
                visited[i][j] = true;
            }
            else if (map[i][j] == 'F') {
                fire.push({ i,j });
            }
        }
        getchar();
    }
    int y, x, ny, nx;
    int time = 1;
    bool failure = true;
    y = person.front().first;
    x = person.front().second;
    //처음부터 경계에 있을때
    if (y == r - 1 || x == c - 1 || y == 0 || x == 0) {
        printf("%d\n", time);
        return 0;
    }
    while (person.size() > 0 && failure)
    {
        time++;
        int s = fire.size();
        //불 먼저 이동
        while (s--)
        {
            y = fire.front().first;
            x = fire.front().second;
            fire.pop();
 
            for (int i = 0; i < 4; i++) {
                ny = y + dy[i];
                nx = x + dx[i];
                if (ny < 0 || ny >= r || nx < 0 || nx >= c || map[ny][nx] == 'F' || map[ny][nx] == '#')continue;
                
                map[ny][nx] = 'F';
                fire.push({ ny,nx });
            }
        }
        //지훈이 이동
        s = person.size();
        while (s-- && failure)
        {
            y = person.front().first;
            x = person.front().second;
            person.pop();
 
            for (int i = 0; i < 4; i++) {
                ny = y + dy[i];
                nx = x + dx[i];
                if (visited[ny][nx] || map[ny][nx] == 'F' || map[ny][nx] == '#')continue;
                if (ny == r - 1 || nx == c - 1 || ny == 0 || nx == 0) {//경계에 도달
                    failure = false;
                    break;
                }
                visited[ny][nx] = true;
                person.push({ ny,nx });
            }
        }
 
    }
    if (failure) {
        printf("IMPOSSIBLE\n");
    }
    else {
        printf("%d\n", time);
    }
 
 
    return 0;
}