백준 3055 - 탈출 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/3055

풀이전략

1. 물의 이동을 잘 파악해야한다. 가로세로 이동하기 때문에 dy, dx를 사용하여 준다. 먼저 물의 이동을 계산하고 이후 고슴도치의 이동을 계산해준다.
2. 고슴도치에 경우 매 분에 따라 움직여야하고, 분에 따라 물의 위치를 최신화 시켜줄때는 분마다 꼭 한번씩만 해주어야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int R, C;
char mp[52][52];
bool ch[53][53];
bool addWater[52][52];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
struct gosem{
    int r, c, val;
    gosem(int aa, int bb, int cc){
        r = aa;
        c = bb;
        val = cc;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    cin >> R >> C;
    int r, c;
    memset(mp, 'Q', sizeof(mp));
    memset(ch, false, sizeof(ch));
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            cin >> mp[i][j];
            if(mp[i][j] == 'S'){
                r = i;
                c = j;
            }
        }
    }
    queue<gosem> q;
    q.push(gosem(r, c, 0));
    ch[r][c] = true; 
    mp[r][c] = '.';
    int val = 0;

    while(!q.empty()){

        gosem ret = q.front();
        q.pop();
        
        memset(addWater, false, sizeof(addWater));

         //// 이부분을 안해줘서 2시간 날림
        //// 처음에 분명히 생각했지만 val에 증가에 따라 물도 증가라고 적었지만 코드구현에서는 잊었다. 코드를 어떻게 짤지 생각할때 더 생각하고 짜야겠다

		// 물의 위치를 최신화 시켜주는 과정
        if(val == ret.val){
            for(int i=1; i<=R; i++){
                for(int j=1; j<=C; j++){
                    if(mp[i][j] == '*'){
                        for(int k=0; k<4; k++){
                            int ii = i+dy[k];
                            int jj = j+dx[k];
                            
                            if(mp[ii][jj] == '.') addWater[ii][jj] = true;
                        }
                    }
                }
            }

            for(int i=1; i<=R; i++){
                for(int j=1; j<=C; j++){
                    if(addWater[i][j] == true){
                        mp[i][j] = '*';
                    }
                }
            }
            // 분마다 한번씩만 해주어야 하기 때문에 이렇게 해줌 
            val++;
        }

        /// 디버깅할떄는 아예 이것처럼 다 출력해보는것도 좋은 아이디어이다.

        // for(int i=1; i<=R; i++){
        //     for(int j=1; j<=C; j++){
        //         if(i == ret.r && j == ret.c) cout<<"S";
        //         else cout<<mp[i][j];
        //     }
        //     cout<<endl;
        // }
		
        // 고슴도치 이동에 관한 것 
        for(int i=0; i<4; i++){
            int rr = ret.r + dy[i];
            int cc = ret.c + dx[i];
            
            if(mp[rr][cc] == 'D'){
                
                cout << ret.val+1 << endl;
                return 0;
            }

            if(!ch[rr][cc] && mp[rr][cc] == '.'){
                ch[rr][cc] = true;
                q.push(gosem(rr, cc, ret.val+1));
            }
        }

    }
    
    cout<<"KAKTUS"<<endl;
    
    return 0;
}

소감

분명히 미리 생각해 두었지만 고슴도치는 4방향으로 움직이므로 방향마다 큐에 들어간다. 그러나 물에 경우는 시간당 한번만 최신화 되어야하므로 둘의 싱크가 안맞을 때가 있다. 따라서 val이라는 변수를 사용하여 해결하였다. 문제를 풀기전에 미리 생각해 두었지만 구현할때는 잊어버렸다. 조금더 정확하게 문제를 구상하고 풀어야겠다.