[백준/c++] 3055번: 탈출

 

https://www.acmicpc.net/problem/3055

3055번: 탈출

 

문제 요약

 

- 지도는 R행 C열로 이루어져 있다.

- 비어있는 곳은 '.' 물이 차있는 곳은 '*' 돌은 'X' 비버의 굴 'D' 고슴도치의 위치 'S'

- 고슴도치는 매 분마다 상하좌우로 이동할 수 있고, 물도 매 분마다 인접 빈칸으로 확장.

- 물과 고슴도치는 돌을 통과 불가

- 고슴도치는 물이 차있는 곳을 통과하지 못하고 물도 비버의 소굴로 이동할 수 없다.

- 고슴도치는 물이 찰 예정인 칸으로 이동 불가(즉, 다음 시간에 물이 찰 예정인 칸으로 이동 불가)

 

고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간은?

(불가하면 KAKTUS 출력)

 

 

범위

 

지도의 행과 열 R, S 모두 50보다 작거나 같은 자연수

 

 

---

 

 

 

고슴도치가 비버의 굴로 최대한 빨리(최소 시간) 이동해야 하므로 BFS를 사용하면 된다. 고슴도치가 이동하는 동시에 물도 차올라야 하기 때문에 이에 따른 BFS도 이루어져야 한다.

즉, 고슴도치의 위치 이동을 위한 BFS와 물의 이동을 위한 BFS 

 

먼저 물을 이동시키고 그 위치에 대한 시간을 저장하자. 다음으로 고슴도치의 비버 소굴로의 최단 거리 이동을 진행하면서 해당 위치에 물이 찼는지 확인하고 차지 않았다면 이동하는 형식으로 진행하면 된다. 

 

 

1. 물 이동 BFS

 

입력받은 지도를 돌면서 물 시작점을 받아와서 queue에 넣어줬다. 

아래의 3개의 조건을 보고 모두 통과하면 이동할 수 있다.

 

- 지도 범위 이탈

- 이미 방문

- 갈 수 없는 곳

 

여기서 water_dist를 기록하는 이유는 바로 고슴도치의 이동 BFS에서 고슴도치가 이동할 수 있는지 확인하기 위해서이다. 이에 대한 내용은 아래의 고슴도치 이동 BFS에서 설명하겠다.

 

void BFS_water(){
    //물은 여러 곳에서 시작할 수 있으므로 모두 queue에 넣고 진행한다
    queue<pair<int, int>> q;
    for(int i=0; i<R; i++) {
        for(int j=0; j<S; j++) {
            water_dist[i][j] = -1;
            if(map[i][j] == '*'){
                q.push({i, j});
                water_dist[i][j] = 0; //방문체크
            }
        }
    }
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if(dx < 0 || dy < 0 || dx >= R || dy >= S) continue; //지도 범위 이탈 pass
            if(water_dist[dx][dy] != -1) continue;               //방문한 곳 pass
            if(map[dx][dy] != '.') continue;                     //갈 수 없는 곳 pass
            water_dist[dx][dy] = water_dist[x][y] + 1;           //시간 기록 -> 고슴도치 이동 시 이동가능한지 체크 O
            q.push({dx, dy});
        }
    }
}

 

 

2. 고슴도치 이동 BFS

 

물의 이동 BFS와 동일하게 진행되지만 한 가지 다른 점(이동 조건)이 존재한다.

if(water_dist[dx][dy] != -1 && water_dist[dx][dy] <= hedgehog_dist[x][y] + 1) continue;

 

바로, 고슴도치가 이동할 수 있는 곳은 

 

- 물에 이미 잠기지 않은 곳

- 물이 차오를 예정이 아닌  곳 

 

여기서 물이 차오를 예정이라는 곳이 안 되는 이유는, 고슴도치가 이동한 곳에 물도 이동해서 차오른다면 고슴도치는 물에 빠지기 때문이다. 😥

 

이를 위해서 

- water_dist [dx][dy] != -1 조건 체크 → -1 이 아니라는 것은 물이 이미 방문한 곳이므로 - 물이 이미 차오른 곳

- water_dist[dx][dy] <= hedgehog_dist [x][y] + 1

  → hedgehog_dist[x][y] + 1 : (x, y) 위치가 물에 잠기는 시간 + 1 (hedgehog_dist [x][y] + 1 : 고슴도치가 다음 판에 이동할 곳) 

  → water_dist [dx][dy] : (dx, dy) 위치가 물에 잠기는 시간

  → 이동할 위치(dx, dy)에 고슴도치가 이동할 시간보다 이동할 위치(dx, dy)가 물에 잠기는 시간이 더 짧다면 이미 물이 차 버린다.

 

 

void BFS_hedgehog(){
    queue<pair<int, int>> q;
    for(int i=0; i<R; i++) {
        for(int j=0; j<S; j++) {
            hedgehog_dist[i][j] = -1;
            if(map[i][j] == 'S'){
                q.push({i, j});
                hedgehog_dist[i][j] = 0;
            }
        }
    }

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if(dx < 0 || dy < 0 || dx >= R || dy >= S) continue;
            if(map[dx][dy] != '.' && map[dx][dy] != 'D') continue;
            if(water_dist[dx][dy] != -1 && water_dist[dx][dy] <= hedgehog_dist[x][y] + 1) continue; //이미 물에 잠긴 곳 (물이 찰 예정인 곳)
            if(hedgehog_dist[dx][dy] != -1) continue; //이미 방문한 곳
            hedgehog_dist[dx][dy] = hedgehog_dist[x][y] + 1;
            q.push({dx, dy});
        }
    }
}

 

 

 

[전체 코드]

#include <iostream>
#include <queue>
using namespace std;
int R, S;
int water_dist[52][52], hedgehog_dist[52][52], dir[4][2] = {{1,0}, {0, 1}, {-1, 0}, {0, -1}};
char map[52][52];

void input(){
    cin >> R >> S;
    for(int i=0; i<R; i++) for(int j=0; j<S; j++) cin >> map[i][j];
}

void BFS_water(){
    //물은 여러 곳에서 시작할 수 있으므로 모두 queue에 넣고 진행한다
    queue<pair<int, int>> q;
    for(int i=0; i<R; i++) {
        for(int j=0; j<S; j++) {
            water_dist[i][j] = -1;
            if(map[i][j] == '*'){
                q.push({i, j});
                water_dist[i][j] = 0; //방문체크
            }
        }
    }
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if(dx < 0 || dy < 0 || dx >= R || dy >= S) continue; //지도 범위 이탈 pass
            if(water_dist[dx][dy] != -1) continue;               //방문한 곳 pass
            if(map[dx][dy] != '.') continue;                     //갈 수 없는 곳 pass
            water_dist[dx][dy] = water_dist[x][y] + 1;           //시간 기록 -> 고슴도치 이동 시 이동가능한지 체크 O
            q.push({dx, dy});
        }
    }
}

void BFS_hedgehog(){
    queue<pair<int, int>> q;
    for(int i=0; i<R; i++) {
        for(int j=0; j<S; j++) {
            hedgehog_dist[i][j] = -1;
            if(map[i][j] == 'S'){
                q.push({i, j});
                hedgehog_dist[i][j] = 0;
            }
        }
    }

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if(dx < 0 || dy < 0 || dx >= R || dy >= S) continue;
            if(map[dx][dy] != '.' && map[dx][dy] != 'D') continue;
            if(water_dist[dx][dy] != -1 && water_dist[dx][dy] <= hedgehog_dist[x][y] + 1) continue; //이미 물에 잠긴 곳 (물이 찰 예정인 곳)
            if(hedgehog_dist[dx][dy] != -1) continue; //이미 방문한 곳
            hedgehog_dist[dx][dy] = hedgehog_dist[x][y] + 1;
            q.push({dx, dy});
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    BFS_water();
    BFS_hedgehog();
    for(int i=0; i<R; i++){
        for(int j=0; j<S; j++) {
            if(map[i][j] == 'D') hedgehog_dist[i][j] == -1 ? cout << "KAKTUS\n" : cout << hedgehog_dist[i][j] << '\n';
        }
    }
    return 0;
}

 

 

 

고슴도치 이동 BFS에서 마지막 조건이 제일 헷갈렸다.. 다시 풀어보도록 하자.🥲

 

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!