백준 4179 불! (bfs)

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

예제 입력 1 복사

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

예제 출력 1 복사

3

 

• 풀이

 

처음에는 지훈이와 불을 동시에 한 큐에 담아서 퍼트리는 bfs인가 했는데 해당 방식으로는 불가능했고

1. 지훈이와 불을 각각 bfs해서 특정 칸 까지 가는데 걸리는 횟수를 구하고

2. 지훈이 위치 기반으로 bfs를 한번 더 하면서 불보다 빠르게 도착했는지를 구하기

위 두 단계로 했고 bfs를 총 3번 했다

 

탈출 조건은 bfs 돌릴때 범위를 벗어나면 탈출하게 되고

불이 아직 퍼지지 않은 칸에 지훈이가 먼저 도착하는 경우까지 생각해줘야 풀렸다..

            //탈출!
            if(dy < 0 || dx < 0 || dy >= n || dx >= m) {
                res = min(res, people[tmp.first][tmp.second]);
                continue;
            }
            // 불보다 지훈이가 늦게 해당 칸에 도착할 수는 없음
            if (fire[dy][dx] != 0){
                if(people[dy][dx] >= fire[dy][dx]) continue;
            }

 

- 전체 코드

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<char>> arr;

int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

// 탈출시간 & 퍼지는 시간 저장할 배열
vector<vector<int>> people;
vector<vector<int>> fire;
vector<vector<bool>> visited;

//지훈이 위치, 불 위치들
pair<int,int> jihun;
vector<pair<int,int>> fires;

int n, m;


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

    cin >> n >> m;
    arr.resize(n,vector<char>(m));
    people.resize(n,vector<int>(m,0));
    fire.resize(n,vector<int>(m,0));
    visited.resize(n,vector<bool>(m,false));

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            arr[i][j] = s[j];
            if(s[j] == 'J') jihun = {i,j};
            if(s[j] == 'F') fires.push_back({i,j});
        }
    }

    queue<pair<int,int>> q1, q2,q3;
    // 지훈이 bfs
    q1.push(jihun);
    people[jihun.first][jihun.second] = 1;
    while (!q1.empty()){
        auto tmp = q1.front();
        q1.pop();
        for(int i = 0; i < 4; i++){
            int dy = tmp.first + dir[i][0];
            int dx = tmp.second + dir[i][1];
            if(dy < 0 || dx < 0 || dy >= n || dx >= m) continue;
            if(people[dy][dx] != 0 ) continue;
            if(arr[dy][dx] == '#') continue;
            people[dy][dx] = people[tmp.first][tmp.second]+1;
            q1.push({dy,dx});
        }
    }

    // 불 bfs
    for(auto x : fires) {
        q2.push(x);
        fire[x.first][x.second] = 1;
    }
    while (!q2.empty()){
        auto tmp = q2.front();
        q2.pop();
        for(int i = 0; i < 4; i++){
            int dy = tmp.first + dir[i][0];
            int dx = tmp.second + dir[i][1];
            if(dy < 0 || dx < 0 || dy >= n || dx >= m) continue;
            if(fire[dy][dx] != 0 ) continue;
            if(arr[dy][dx] == '#') continue;
            fire[dy][dx] = fire[tmp.first][tmp.second]+1;
            q2.push({dy,dx});
        }
    }

    int res = INT32_MAX;
    // 불, 지훈이 최단거리 기반 bfs
    q1.push(jihun);
    visited[jihun.first][jihun.second] = true;
    while (!q1.empty()){
        auto tmp = q1.front();
        q1.pop();
        for(int i = 0; i < 4; i++){
            int dy = tmp.first + dir[i][0];
            int dx = tmp.second + dir[i][1];
            //탈출!
            if(dy < 0 || dx < 0 || dy >= n || dx >= m) {
                res = min(res, people[tmp.first][tmp.second]);
                continue;
            }
            if(visited[dy][dx]) continue;
            if(arr[dy][dx] == '#') continue;
            // 불보다 지훈이가 늦게 해당 칸에 도착할 수는 없음
            if (fire[dy][dx] != 0){
                if(people[dy][dx] >= fire[dy][dx]) continue;
            }
            visited[dy][dx] = true;
            q1.push({dy,dx});
        }
    }

    if(res != INT32_MAX) cout << res;
    else cout << "IMPOSSIBLE";
    return 0;
}