[5427번] 불

문제 출처 :

https://www.acmicpc.net/problem/5427

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

이 문제를 풀기 전, [4179번] Fire! :: http://www.crocus.co.kr/714를 풀고 이 문제를 풀기를 권장한다.

위의 문제와 아에 똑같은 문제인데 이번 문제는 테스트 케이스가 존재하는 것만 다르다.

이전 게시물과 동일하게 두번의 BFS로 해결한다.

첫번째는 불길이 각 위치에 도달하는 시간을 visit[][]에 표시해 줌으로써 불의 시간정보를 표시해주고

두번째는 상근이가 움직이는데 불보다 빠르게 움직이는지 느리게 움직이는지 BFS로 판단해주면 된다.

불이 났다면 find = false, 불이 나지 않았다면 find = true로 해결한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
 
using namespace std;
 
typedef struct _INFO_
{
    int y;
    int x;
    int cnt;
}INFO;
 
char str[1005][1005];
int visit[1005][1005];
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
    
    while (tCase--)
    {
        int n, m;
        int jx, jy;
        queue<INFO> q;
 
        scanf("%d %d", &n, &m);
 
 
        // 맵 입력
        getchar();
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
                scanf("%c", &str[i][j]);
 
            getchar();
        }
 
        for (int i = 0; i <= m + 1; i++)
        {
            str[i][0] = '$';
            str[i][n + 1] = '$';
        }
 
        for (int j = 0; j <= n + 1; j++)
        {
            str[0][j] = '$';
            str[m + 1][j] = '$';
        }
 
        memset(visit, 0, sizeof(visit));
 
        // #이면 visit에는 -1로, @면 상근이의 위치 받아내고, 
        // *이면 불이난 위치의 값을 queue에 넣는다.
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (str[i][j] == '#')
                    visit[i][j] = -1;
 
                else if (str[i][j] == '@')
                {
                    jx = j;
                    jy = i;
                }
                else if (str[i][j] == '*')
                    q.push(INFO{ i,j,1 });
            }
        }
 
        // 불이 번지는 위치에 걸린 시간을 기입한다.
        while (!q.empty())
        {
            int y = q.front().y;
            int x = q.front().x;
            int cnt = q.front().cnt;
 
            q.pop();
 
            if (visit[y][x])
                continue;
 
            visit[y][x] = cnt;
 
            // . 또는 @는 통행 가능 길
            if (y - 1 >= 1 && !visit[y - 1][x] && (str[y - 1][x] == '.' || str[y - 1][x] == '@'))
                q.push(INFO{ y - 1, x, cnt + 1 });
 
            if (y + 1 <= m && !visit[y + 1][x] && (str[y + 1][x] == '.' || str[y + 1][x] == '@'))
                q.push(INFO{ y + 1, x, cnt + 1 });
 
            if (x - 1 >= 1 && !visit[y][x - 1] && (str[y][x - 1] == '.' || str[y][x - 1] == '@'))
                q.push(INFO{ y, x - 1, cnt + 1 });
 
            if (x + 1 <= n && !visit[y][x + 1] && (str[y][x + 1] == '.' || str[y][x + 1] == '@'))
                q.push(INFO{ y, x + 1, cnt + 1 });
        }
    
        // 상근이의 위치와 시간을 넣어준다.
        q.push(INFO{ jy,jx,1 });
        bool find = false;
 
        while (!q.empty())
        {
            if (find == true)
            {
                q.pop();
                continue;
            }
 
            int y = q.front().y;
            int x = q.front().x;
            int cnt = q.front().cnt;
 
            q.pop();
 
            // 상근이가 $로 왔을 때 탈출했다는 의미
            if (str[y + 1][x] == '$' || str[y - 1][x] == '$' || str[y][x - 1] == '$' || str[y][x + 1] == '$')
            {
                printf("%d\n", cnt);
                find = true;
                continue;
            }
 
            // 불길이 도착한 시간 이상이고, visit[y][x]가 0이 아니면
            // 즉, visit[][] = 0인경우는 불이 번지지 않은 위치를 의미 
            if (visit[y][x] <= cnt && visit[y][x] != 0)
                continue;
 
            // 상근이의 위치를 -2로 표시
            visit[y][x] = -2;
 
            // 불보다 먼저 상근이가 왔거나, 그 위치의 visit[][]가 0이면
            if (y - 1 >= 1 && (visit[y - 1][x] > cnt + 1 || visit[y-1][x] == 0))
                q.push(INFO{ y - 1, x, cnt + 1 });
 
            if (y + 1 <= m && (visit[y + 1][x] > cnt + 1 || visit[y + 1][x] == 0))
                q.push(INFO{ y + 1, x, cnt + 1 });
 
            if (x - 1 >= 1 && (visit[y][x - 1] > cnt + 1 || visit[y][x - 1] == 0))
                q.push(INFO{ y, x - 1, cnt + 1 });
 
            if (x + 1 <= n && (visit[y][x + 1] > cnt + 1 || visit[y][x + 1] == 0))
                q.push(INFO{ y, x + 1, cnt + 1 });
        }
 
        // 큐를 모두 수행할 동안 $를 못만나면 결국 impossible한 것
        if(find == false)
            printf("IMPOSSIBLE\n");
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>