[백준 3197] 백조의 호수 (BFS) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
char map[1510][1510];
int row, col;
int swanX, swanY;
int day;
bool flag = false;
 
queue<pair<int, int>> m;
 
queue<pair<int, int>> reserve;
int visiteds[1510][1510];
 
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 melt()
{
    int cnt = m.size();
    
    while(cnt--)
    {
        int x = m.front().first;
        int y = m.front().second;
        m.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')
            {
                m.push({xpos, ypos});
                map[xpos][ypos] = '.';
            }
        }
    }
}
 
void swan()
{    
    queue<pair<int, int>> s;
    s = reserve;
    
    // <reserve queue> clear
    queue<pair<int, int>> empty;
    swap(empty, reserve);
    
    while(!s.empty())
    {
        int x = s.front().first;
        int y = s.front().second;
        s.pop();
        
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visiteds[xpos][ypos] == 0 && map[xpos][ypos] == '.')
            {
                visiteds[xpos][ypos] = 1;
                s.push({xpos, ypos});
            }
            else if(safe(xpos, ypos) == 1 && visiteds[xpos][ypos] == 0 && map[xpos][ypos] == 'L')
            {
                visiteds[xpos][ypos] = 1;
                s.push({xpos, ypos});
                
                flag = true;
                return;
            }
            // 상하좌우가 X면 백조가 더이상 못가기 때문에, 백조 위치 저장 
            else if(safe(xpos, ypos) == 1 && visiteds[xpos][ypos] == 0 && map[xpos][ypos] == 'X')
            {
                reserve.push({x, y});
            }
        }
    }
}
 
void print()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
int main(void)
{
//    freopen("B3197_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            
            // 백조도 물로 친다(중요) 
            if(map[i][j] == '.' || map[i][j] == 'L')
            {
                m.push({i, j});
            }
            
            if(map[i][j] == 'L')
            {
                swanX = i;
                swanY = j;
            }
        }
    }
    
    // 백조 초기 시작값 저장 
    reserve.push({swanX, swanY});
    visiteds[swanX][swanY] = 1;
 
    while(1)
    {
        day++;
        
        melt();
    
        swan();
        
//        print();
        
        if(flag == true)
        {
            cout << day << "\n";
            break;
        }    
    }
        
    return 0;
}