[백준 3055] 탈출 C++

3055번: 탈출

BFS

---

1. 문제 해결 아이디어

 

5427번: 불

 

위 문제랑 거의 똑같은듯 하다

 

 

고슴도치는 물이 곧 차오를 지역으로 가지 못하기 때문에 bfs를 통해서 물을 먼저 채워준다

이때 채워진 물을 nextwater 큐에 넣어준다.

물은 . 부분에만 채워질 수 있다.

 

물을 채웠다면 고슴도치를 움직여 보자

고슴도치는 다음칸이 . 이나 D인 경우에만 이동할 수 있다.

이동할 수 있다면 nextgosm 큐에 넣어준다.

 

물을 채워주고, 고슴도치가 이동할 수 있는 경우를 모두 큐에 넣었다면

next큐들을 gosm, water큐에 각각 대입해주고 next큐들을 비워준다.

 

 

 - 고슴도치가 이동중에 D를 만난다면 현재 이동횟수가 최솟값이기 때문에 즉시 종료한다.

 - 끝까지 만나지 못한다면 KAKTUS

 

---

2. 코드

#include <iostream>
#include <queue>
#include <cstring>
 
#define pii pair<int, int>
 
using namespace std;
 
int R, C;
// *:0  .:1  S:1  D:2  X:3
int Map[51][51];
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
bool visited[51][51];
pii beaver;
 
queue<pii > water;
queue<pii > gosm;
 
 
void input(){
    string str;
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        cin >> str;
        for(int j = 0; j < str.size(); j++){
            if(str[j] == 'D'){
                Map[i][j] = 2;
                beaver = {i, j};
            }
            else if(str[j] == '.'){
                Map[i][j] = 1;
            }
            else if(str[j] == 'S'){
                gosm.push({i, j});
                Map[i][j] = 1;
                visited[i][j] = true;
            }
            else if(str[j] == '*'){
                Map[i][j] = 0;
                water.push({i, j});
            }
            else if(str[j] == 'X'){
                Map[i][j] = 3;
            }
        }
    }
}
 
int BFS(){
    queue<pii > nextwater, nextgosm;
    int cnt = 0;
    
    while(!gosm.empty()){
        
        // 물 먼저 차오름
        while(!water.empty()){
            pii now = water.front();
            water.pop();
            
            for(int k = 0; k < 4; k++){
                int nr = now.first + dr[k];
                int nc = now.second + dc[k];
                
                if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if(Map[nr][nc] != 1) continue;
                
                nextwater.push({nr, nc});
                Map[nr][nc] = 0;
            }
            
        }
        
        // 고슴도치 이동
        while(!gosm.empty()){
            pii now = gosm.front();
            gosm.pop();
            
            if(now.first == beaver.first && now.second == beaver.second) return cnt;
            
            for(int k = 0; k < 4; k++){
                int nr = now.first + dr[k];
                int nc = now.second + dc[k];
                
                if(nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]) continue;
                if(Map[nr][nc] != 1 && Map[nr][nc] != 2) continue;
                
                visited[nr][nc] = true;
                nextgosm.push({nr, nc});
            }
        }
        
        cnt++;
        water = nextwater;
        while(!nextwater.empty()) nextwater.pop();
        gosm = nextgosm;
        while(!nextgosm.empty()) nextgosm.pop();
    }
    
    return -1;
}
 
void solve(){
    int res = BFS();
    
    if(res == -1) cout << "KAKTUS";
    else cout << res;
}
 
int main(){
    input();
    solve();
    
    return 0;
}
 

 

내 설명이 너무 구리다ㅠ