[백준 5427] 불

백준 5427 불

이 문제는 상근(@)이가 안전하게 맵 밖으로 나가면 된다. 문제를 보면 불(*)이 붙으려는 칸으로 이동할 수 없다고 한다. 이를 알고리즘으로 해결하기 위해서는 불부터 이동시키고 그다음 상근이를 이동시키면 된다.

일단 먼저 맵의 정보를 읽으면서 불의 위치와 상근이의 위치를 각각 큐에 넣는다. 상근이의 위치가 들어 있는 큐의 크기가 0일 때까지 불을 한칸씩 이동시키고 상근이의 위치를 한 칸씩 이동시키면 된다. 이를 반복하다가 상근이가 맵 밖으로 나간다면 상근이가 이동한 횟수를 출력하면 되고 상근이의 위치가 담긴 큐의 크기가 0일 때까지 반복하는데 상근이가 맵 밖으로 못나갔으면 IMPOSSIBLE을 출력하면 된다.

#include<cstdio>
#include<iostream>
#include<queue>
 
using namespace std;
 
char map[1001][1001] = { 0 };
queue<pair< pair<int, int>, int>> men;
queue<pair<int, int>> fire;
 
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
bool check = false;
 
int main()
{
    int TestCase;
    scanf("%d", &TestCase);
    for (; TestCase--;)
    {
        int w, h;
        scanf("%d %d", &w, &h);
        for (int i = 0; i < h; i++)
        {
            scanf("%s", map[i]);
            for (int j = 0; map[i][j]; j++)
            {
                if (map[i][j] == '@')
                {
                    men.push(make_pair(make_pair(i, j), 0));
                }
                else if (map[i][j] == '*')
                {
                    fire.push(make_pair(i, j));
                }
            }
        }
        check = false;
        while (1)
        {
            int size;
            int qx, qy, count;
            size = fire.size();
            while (size--) {
                qx = fire.front().second;
                qy = fire.front().first;
                fire.pop();
 
                for (int i = 0; i < 4; i++)
                {
                    if (qx + dx[i] < 0 || qx + dx[i] >= w || qy + dy[i] < 0 || qy + dy[i] >= h)continue;
                    if (map[qy + dy[i]][qx + dx[i]] == '.' || map[qy + dy[i]][qx + dx[i]] == '@')
                    {
                        map[qy + dy[i]][qx + dx[i]] = '*';
                        fire.push(make_pair(qy + dy[i], qx + dx[i]));
                    }
                }
            }
 
            size = men.size();
            while (size--) {
                qx = men.front().first.second;
                qy = men.front().first.first;
                count = men.front().second;
                men.pop();
 
                for (int i = 0; i < 4; i++)
                {
                    if (qx + dx[i] < 0 || qx + dx[i] >= w || qy + dy[i] < 0 || qy + dy[i] >= h)
                    {
                        check = true;
                        break;
                    }
                    if (map[qy + dy[i]][qx + dx[i]] == '.')
                    {
                        map[qy + dy[i]][qx + dx[i]] = '@';
                        men.push(make_pair(make_pair(qy + dy[i], qx + dx[i]), count + 1));
                    }
                }
            }
            if (check == true)
            {
                printf("%d\n", count + 1);
                while (!men.empty())men.pop();
                while (!fire.empty())fire.pop();
                break;
            }
            if (men.empty())
            {
                while (!men.empty())men.pop();
                while (!fire.empty())fire.pop();
                printf("IMPOSSIBLE\n");
                break;
            }
            
        }
 
    }
    return 0;
}

이 문제와 거의 같은 문제가 있다. 그 문제는 불! 이라는 문제이다. 불! 문제도 이 문제와 거의 같은 방식으로 푸는 문제인걸로 기억한다.