[백준 3055] 탈출 (BFS) (C/C++) (★)

#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
char map[55][55];
int row, col;
int endX, endY;
int time;
 
queue<pair<int, int>> h;
int visitedh[55][55];
 
queue<pair<int, int>> w;
int visitedw[55][55];
 
int dx[4] = {-1, 1, 0 ,0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void water()
{
    // 한턴만 BFS 수행하기 위해서 size만큼 고정 
    int cnt = w.size();
    
    while(cnt--)
    {
        int x = w.front().first;
        int y = w.front().second;
        w.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            // 물이 참과 동시에 고슴도치도 이동하기 때문에 고슴도치가 현재 있는곳도 체크 
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 'X' && map[xpos][ypos] != 'D' && visitedw[xpos][ypos] == 0)
            {
                map[xpos][ypos] = '*';
                
                visitedw[xpos][ypos] = 1;
                w.push({xpos, ypos});
            }
        }
    }
}
 
void hedgehog()
{
    // 한턴만 BFS 수행하기 위해서 size만큼 고정 
    int cnt = h.size();
    
    while(cnt--)
    {
        int x = h.front().first;
        int y = h.front().second;
        h.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && (map[xpos][ypos] == '.' || map[xpos][ypos] == 'D') && visitedh[xpos][ypos] == 0)
            {
                visitedh[xpos][ypos] = 1;
                h.push({xpos, ypos});
            }
        }
    }
}
 
int main(void)
{
//    freopen("B3055_input.txt", "r", stdin);
    
    scanf("%d %d", &row, &col);
 
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == '*')
            {
                visitedw[i][j] = 1;
                w.push({i, j});
            }
            else if(map[i][j] == 'S')
            {
                visitedh[i][j] = 1;
                h.push({i, j});
            }
            else if(map[i][j] == 'D')
            {
                endX = i;
                endY = j;
            }
        }
    }
    
    while(1)
    {    
        if(visitedh[endX][endY] == 1)
        {
            cout << time << endl;
            return 0;
        }
        
        if(h.empty())
        {
            cout << "KAKTUS" << endl;
            return 0;
        }
        
        water();
        hedgehog();
        
        time++;
    }
        
    return 0;
}