백준 5427번 문제 ( 불 )

문제 출처 : https://www.acmicpc.net/problem/5427

5427번: 불

이 문제는 BFS를 이용하여 문제를 해결 할 수 있었다.

방문 배열을 사람과 불이 이동한 것을 따로 두어서 불이 먼저 이동하고 사람이 이동하는 식으로 문제를 해결했다. 

그렇게 되면 불이 지나가려는 곳을 사람이 못 가게 할 수 있고 탈출구 까지 편안하게 이동 할 수 있다.

아래는 해당 문제를 풀이한 소스 코드이다.

#include<stdio.h>
#include<queue>
#pragma warning(disable:4996)
using namespace std;
int Test;
int w, h;
int visit[1001][1001];
char arr[1001][1001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int flag = 0;
struct list
{
    int x;
    int y;
    int cnt = 0;
};
queue <list> fire;
queue <list> human;
void Fire()
{
    int size = fire.size();
    for (int i = 0; i < size; i++)
    {
        list temp = fire.front();
        fire.pop();
        for (int j = 0; j < 4; j++)
        {
            int nx = temp.x + dx[j];
            int ny = temp.y + dy[j];
            if (nx >= 0 && nx < h && ny >= 0 && ny < w)
            {
                if (arr[nx][ny] == '.' && visit[nx][ny] != 2)
                {
                    arr[nx][ny] = '*';
                    visit[nx][ny] = 2;
                    list A;
                    A.x = nx;
                    A.y = ny;
                    fire.push(A);
                }
                if (arr[nx][ny] == '@' && visit[nx][ny] != 2)
                {
                    arr[nx][ny] = '*';
                    visit[nx][ny] = 2;
                    list A;
                    A.x = nx;
                    A.y = ny;
                    fire.push(A);
                }
            }
        }
    }
}
void escape()
{
    int size = human.size();
    for (int i = 0; i < size; i++)
    {
        list temp = human.front();
        human.pop();
        for (int j = 0; j < 4; j++)
        {
            int nx = temp.x + dx[j];
            int ny = temp.y + dy[j];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
            {
                flag = 1;
                printf("%d\n", temp.cnt + 1);
                return;
            }
            if (nx >= 0 && nx < h && ny >= 0 && ny < w)
            {
                if (arr[nx][ny] == '.' && visit[nx][ny] == 0)
                {
                    visit[nx][ny] = 1;
                    list A;
                    A.x = nx;
                    A.y = ny;
                    A.cnt = temp.cnt + 1;
                    human.push(A);
                }
            }
        }
    }
}
void reset()
{
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            visit[i][j] = 0;
            arr[i][j] = ' ';
        }
    }
    flag = 0;
    while (!fire.empty())
        fire.pop();
    while (!human.empty())
        human.pop();
}
int main()
{
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    scanf("%d", &Test);
    for (int i = 0; i < Test; i++)
    {
        scanf("%d %d", &w, &h);
        for (int j = 0; j < h; j++)
            scanf("%s", &arr[j]);
        for (int j = 0; j < h; j++)
        {
            for (int k = 0; k < w; k++)
            {
                if (arr[j][k] == '*')
                {
                    visit[j][k] = 2;
                    list temp;
                    temp.x = j;
                    temp.y = k;
                    fire.push(temp);
                }
                if (arr[j][k] == '@')
                {
                    visit[j][k] = 1;
                    list temp;
                    temp.x = j;
                    temp.y = k;
                    human.push(temp);
                }
            }
        }
        while (!human.empty())
        {
            if (flag == 1)
                break;
            Fire();
            escape();
        }
        if (flag == 0)
            printf("IMPOSSIBLE\n");
        reset();
    }
}