[bfs] 백준 3055 탈출

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

매분이 지날 때 마다 물을 확장 시킵니다.

그리고 고슴도치가 이동합니다.

이런 식으로 해서 풀었습니다. 좀 난잡하네요. visited가 없어도 될 것 같기도 한데...

#include <iostream>
#include <queue>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    pair<int,int> ans;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    int min = 0;
    char map[51][51];
    bool visited[51][51] = {};
    int R,C;
    queue<pair<int,int>> S; //x,y
    queue<pair<int,int>> water;
    cin >> R >> C;
    
    for(int i = 0; i < R; i++){
        for(int j = 0; j <C; j++){
            cin >> map[i][j];
            if(map[i][j] == 'S') {S.push({j,i}); visited[i][j] = 1;}
            else if(map[i][j] == '*') water.push({j,i});
            else if(map[i][j] == 'D') ans = {j,i};
        }
    }
    
    while(!S.empty()){
        if(visited[ans.second][ans.first]) break;
        
        min+=1;
        
        pair<int,int> tmp;
        int water_size = water.size();
        for(int i = 0; i < water_size; i++){
            tmp = water.front();
            water.pop();
            for(int j = 0; j < 4; j++){
                int x = tmp.first+dx[j];
                int y = tmp.second+dy[j];
                if(y >= R || x >= C || y <0 || x < 0 || map[y][x] != '.') 
                    continue;
                water.push({x,y}); map[y][x] = '*';
            }
        }
        
        int S_size = S.size();
        for(int i = 0; i < S_size; i++){
            if(visited[ans.second][ans.first]) break;
            tmp = S.front();
            S.pop();
            for(int j = 0; j < 4; j++){
                int x = tmp.first+dx[j];
                int y = tmp.second+dy[j];
                
                if(y >= R || x >= C || y <0 || x < 0 || visited[y][x])
                    continue;
                
                if(map[y][x] != '.'){
                    if(map[y][x] == 'D') {
                        visited[y][x] = 1; 
                        break;
                    }
                    continue;
                }
                
                visited[y][x] = 1;
                S.push({x,y});
            }
        }
    }
    
    
    if(visited[ans.second][ans.first]) cout << min;
    else cout << "KAKTUS";
    
}