백준 3055번 탈출 - C++(cpp) 풀이

---

 

1. 물의 확장을 BFS로 시뮬레이션해서 각 빈칸에 물이 몇 분에 도착하는지 기록한다.
2. 고슴도치의 이동을 BFS로 시뮬레이션한다. 물이 도착하기 전에 이동할 수 있는 곳으로만 계속 이동한다.
3. 2번 과정에서 비버의 굴에 도착하면 그 시간을 출력한다.

 

1. 물의 확장을 BFS로 시뮬레이션해서 각 빈칸에 물이 몇 분에 도착하는지 기록한다.

 물이 매 분 인접한 한 칸으로 확장되므로 너비우선탐색(BFS)로 시뮬레이션 할 수 있다. BFS에서의 depth가 곧 해당 칸에 물이 도착하기까지 걸리는 시간이다.

 

2. 고슴도치의 이동을 BFS로 시뮬레이션한다. 물이 도착하기 전에 이동할 수 있는 곳으로만 계속 이동한다.

 고슴도치도 매 분 인접한 한 칸으로 이동하므로 BFS로 시뮬레이션할 수 있다. 인접한 칸으로 이동하기 전에 해당 칸에 물이 몇 분에 도착하는지 체크한다. 고슴도치가 물보다 먼저 도착할 수 있는 경우에만 해당 칸으로 이동한다.

 

3. 2번 과정에서 비버의 굴에 도착하면 그 시간을 출력한다.

 고슴도치 이동 시뮬레이션 중에 비버의 굴에 도착하면 고슴도치가 해당 칸에 도착하기까지 걸린 시간을 출력해주면 된다.

반응형

---

#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>

using namespace std;

int INF = 987654321;
int R, C;
int hedgehog_r, hedgehog_c;     // 고슴도치 처음 위치

char map[50][50];
int water_visit[50][50];        // 물이 해당 칸에 몇 분에 도착하는지
int hedgehog_visit[50][50];     // 고슴도치가 해당 칸에 몇 분에 도착하는지

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int move_hedgehog() {
    queue<pair<int, int>> q;
    
    q.push({hedgehog_r, hedgehog_c});
    hedgehog_visit[hedgehog_r][hedgehog_c] = 1;
    
    while (!q.empty()) {
        int curr_r = q.front().first;
        int curr_c = q.front().second;
        q.pop();
        
        if (map[curr_r][curr_c] == 'D') return hedgehog_visit[curr_r][curr_c] - 1;
        
        for(int i=0; i<4; i++) {
            int next_r = curr_r + dr[i];
            int next_c = curr_c + dc[i];
            
            if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue;
            if (hedgehog_visit[next_r][next_c]) continue;
            if (map[next_r][next_c] == 'X') continue;
            
            // 해당 칸에 물이 도착하기 전에 도치가 더 빨리 도착할 수 있다면 이동
            if (water_visit[next_r][next_c] > hedgehog_visit[curr_r][curr_c] + 1) {
                q.push({next_r, next_c});
                hedgehog_visit[next_r][next_c] = hedgehog_visit[curr_r][curr_c] + 1;
            }
        }
    }
    
    return 987654321;
}

void flow_water(int r, int c) {
    queue<pair<int, int>> q;
    
    q.push({r, c});
    water_visit[r][c] = 1;
    
    while (!q.empty()) {
        int curr_r = q.front().first;
        int curr_c = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++) {
            int next_r = curr_r + dr[i];
            int next_c = curr_c + dc[i];
            
            if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue;
            if (map[next_r][next_c] == 'X' || map[next_r][next_c] == 'D') continue;
            if (water_visit[next_r][next_c] <= water_visit[curr_r][curr_c] + 1) continue;
            
            q.push({next_r, next_c});
            water_visit[next_r][next_c] = water_visit[curr_r][curr_c] + 1;
        }
    }
}

int simulate() {
    for(int i=0; i<50; i++) {
        for(int j=0; j<50; j++) {
            water_visit[i][j] = INF;
        }
    }
    
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            if (map[i][j] != '*') continue;
            flow_water(i, j);
        }
    }
    
    return move_hedgehog();
}

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

    cin >> R >> C;
    
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            cin >> map[i][j];
            
            if (map[i][j] == 'S') {
                hedgehog_r = i;
                hedgehog_c = j;
            }
        }   
    }
    
    int result = simulate();
    
    if (result == INF) cout << "KAKTUS";
    else cout << result;

    return 0;
}