[BOJ] 3055. 탈출

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

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
char map[51][51];
int n,m;
queue<pair<int,int>> w_q;
queue<pair<int,int>> s_q;

int main(){
    pair<int, int> d; // d is Destination
    
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            scanf(" %c", &c);
            if( c == '*'){
                map[i][j] = '*';
                w_q.push({i,j});
            }
            else if ( c == 'S'){
                map[i][j] = 'S';
                s_q.push({i,j});
            }
            else if ( c == 'D'){
                map[i][j] = 'D';
                d = {i,j};
            }
            else if ( c == 'X'){
                map[i][j] = 'X';
            }
            else
                map[i][j] = '.';
        }
    }
    
    int ans=0;
    
    while (! s_q.empty()) {
        int nx,ny;
        int w_size = (int) w_q.size();
        int s_size = (int) s_q.size();
        ans ++;
        for(int i=0; i<s_size; i++){
            int s_x = s_q.front().first;
            int s_y = s_q.front().second;
            s_q.pop();
            
            if( map[s_x][s_y] != 'S') continue;
            
            for(int j=0; j<4; j++){
                nx = s_x + dx[j];
                ny = s_y + dy[j];
                
                if( map[nx][ny] == '.' ){
                    map[nx][ny] = 'S';
                    s_q.push({nx,ny});
                }
                
                if( map[nx][ny] == 'D'){
                    cout << ans << endl;
                    return 0;
                }
            }
        }
        
        for(int i=0; i<w_size; i++){
            int w_x = w_q.front().first;
            int w_y = w_q.front().second;
            w_q.pop();
            
            for(int j=0; j<4; j++){
                nx = w_x + dx[j];
                ny = w_y + dy[j];
                
                if( map[nx][ny] == '.' || map[nx][ny] == 'S' ){
                    map[nx][ny] = '*';
                    w_q.push({nx,ny});
                }
            }
        }
    }
    
    cout << "KAKTUS" << endl;
    
    return 0;
}