[백준 5427] 불 (BFS) (C/C++) (★)

 
#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
char map[1010][1010];
int row, col;
int T;
int endX, endY;
bool flag = false;
 
queue<pair<int, int>> s;
int visiteds[1010][1010];
 
queue<pair<int, int>> f;
int visitedf[1010][1010];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
void init()
{
    // swap을 통한 queue 비우기 -> pop 반복을 통해서도 가능 
    queue<pair<int, int>> empty1;
    swap(s, empty1);
    
    queue<pair<int, int>> empty2;
    swap(f, empty2);
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            visiteds[i][j] = 0;
            visitedf[i][j] = 0;
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void fire()
{
    int cnt = f.size();
    
    while(cnt--)
    {
        int x = f.front().first;
        int y = f.front().second;
        f.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && visitedf[xpos][ypos] == 0 && map[xpos][ypos] != '#')
            {
                map[xpos][ypos] = '*';
                
                visitedf[xpos][ypos] = 1;
                f.push({xpos, ypos});
            }
        }    
    }
}
 
void sang()
{
    int cnt = s.size();
    
    while(cnt--)
    {
        int x = s.front().first;
        int y = s.front().second;
        s.pop();
        
        if(x == 0 || y == 0 || x == row-1 || y == col-1)
        {
            flag = true;
            endX = x;
            endY = y;
            
            return;
        }
        
        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] = visiteds[x][y] + 1;
                s.push({xpos, ypos});
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B5427_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int n = 1; n <= T; n++)
    {
        flag = false;
        
        cin >> col >> row;
        
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                cin >> map[i][j];
                
                if(map[i][j] == '*')
                {
                    visitedf[i][j] = 1;
                    f.push({i, j});
                }
                else if(map[i][j] == '@')
                {
                    visiteds[i][j] = 1;
                    s.push({i, j});
                }
            }
        }
        
        int time = 0;
        while(1)
        {
            if(flag == true)
            {
                cout << visiteds[endX][endY] << endl;
                break;
            }
            
            if(s.empty())
            {
                cout << "IMPOSSIBLE" << endl;
                break;
            }
            
            fire();
            sang();
        }
 
        init();
    }
        
    return 0;
}