[BOJ 3055] 탈출 (C++)

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

3055번: 탈출

 

#include <bits/stdc++.h>
using namespace std;
 
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
 
class Pos{
    public:
        int y,x;
        Pos(int r, int c){
            y=r;
            x=c;
        }
};
 
int main(){
    char c;
    int R,C;
    cin>>R>>C;
    char map[R][C];
    int dp[R][C];
    queue<Pos> q;
    int tx, ty, dest_x, dest_y;
    for (int i=0; i<R; i++){
        for (int j=0; j<C; j++){
            cin>>c;
            map[i][j]=c;
            dp[i][j]=0;
            if (c=='*'){
                q.push(Pos(i,j));
            }
            if (c=='S'){
                ty=i;
                tx=j;
            }
            if (c=='D'){
                dest_y=i;
                dest_x=j;
            }
        }
    }
    q.push(Pos(ty,tx));
    while (!q.empty()){
        ty=q.front().y;
        tx=q.front().x;
        q.pop();
        if (ty==dest_y && tx==dest_x){
            cout<<dp[ty][tx]<<endl;
            return 0;
        }
        for (int i=0; i<4; i++){
            int nx=tx+dx[i];
            int ny=ty+dy[i];
            if (ny<0 || nx<0 || ny>=R || nx>=C){
                continue;
            }
            if (map[ty][tx]=='*'){
                if (map[ny][nx]=='.' && dp[ny][nx]==0){
                    map[ny][nx]='*';
                    q.push(Pos(ny,nx));
                }
            }
            else{
                if (map[ny][nx]=='.' || map[ny][nx]=='D'){
                    if (dp[ny][nx]==0){
                        dp[ny][nx]=dp[ty][tx]+1;
                        q.push(Pos(ny,nx));
                    }
                }
            }
        }
    }
    cout<<"KAKTUS"<<endl;
    return 0;
}

BFS 문제.

고슴도치+물을 동시에 움직여야 하는 문제 때문에 많이 고심함.

근데 해답은!

물 먼저 움직이면, 물이 차오를 예정인 칸은 고슴도치가 제외시킬 수 있다.

즉 큐를 시작할 때 물이 있는 위치를 먼저 다 넣고 마지막에 고슴도치의 위치를 넣어준다.

그렇게 하면 물이 먼저 움직이게 되고, 차오를 부분은 미리 차오르기 때문에 "차오를 예정인 칸"은 고슴도치가 알아서 자동으로 피할 수 있다.

BFS 는 다음을 기억한다.

1. 큐에서 꺼내옴

2. 목적지인가?

3. 갈 수 있는 곳을 순회

4. 갈 수 있는가?

5. 체크인

6. 큐에 넣음

여기서 갈 수 있는가의 문제는 물/고슴도치로 분기한다. 물일 경우 빈칸이고, dp배열이 0인 곳(즉 방문하지 않은 곳)을 방문하고

고슴도치일 경우 dp배열 0, 빈칸, 목적지일때 방문하고 큐에 넣는다.

 

dp배열을 만들어줌으로써 방문 표시+거리 카운팅 동시에 할 수 있다.

이 아이디어를 기억하자.

 

시작점에 먼저 물을 넣고, 고슴도치를 넣으면 해결딘다.