[알고리즘] 백준 3055 - 탈출

#include <iostream>
#include <queue>
using namespace std;

int R, C, T;
bool goal;
char Arr[51][51];
bool QC[51][51];
bool WC[51][51];
int Dir[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
queue<pair<int, int>> Q;
queue<pair<int, int>> W;

void water(){
    int sz = W.size();
    while(sz--){
        int y = W.front().first;
        int x = W.front().second;
        W.pop();

        for(int d=0; d<4; d++){
            int ny = y + Dir[d][0];
            int nx = x + Dir[d][1];

            if(ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
            if(Arr[ny][nx] == 'X' || Arr[ny][nx] == 'D' || WC[ny][nx] == true) continue;
            W.push({ny, nx});
            WC[ny][nx] = true;
            Arr[ny][nx] = '*';
        }
    }
    return;
}

void move(){
    int sz = Q.size();
    while(sz--){
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();

        for(int d=0; d<4; d++){
            int ny = y + Dir[d][0];
            int nx = x + Dir[d][1];
            
            if(ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
            if(Arr[ny][nx] == 'X' || Arr[ny][nx] == '*' || QC[ny][nx] == true) continue;
            if(Arr[ny][nx] == 'D'){
                goal = true;
                return;
            }
            Q.push({ny, nx});
            QC[ny][nx] = true;
        }
    }
    return;
}

void solve(){
    while(Q.empty() == false){
        water();
        move();
        T++;
        if(goal == true){
            cout << T << "\n";
            return;
        }
    }
    cout << "KAKTUS\n";
    return;
}

int main(){
    cin >> R >> C;
    string S;
    for(int i=0; i<R; i++){
        cin >> S;
        for(int j=0; j<C; j++){
            Arr[i][j] = S[j];
            if(S[j] == 'S'){
                Q.push({i, j});
                QC[i][j] = true;
            }
            if(S[j] == '*'){
                W.push({i, j});
                WC[i][j] = true;
            }
        }
    }

    solve();

    return 0;
}