[BEAKJOON] 5427_불_C언어

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

풀이

얼마전에 풀었던 3055번 탈출과 매우 유사한 문제라 풀이를 생략한다.

문제 푸는데 헛짓을 좀 해서...시간을 많이 소비했더니 피곤하다.....

궁금하게 하나 있는데...상근이가 먼저 이동하고 불이 퍼져도 맞다고 생각되는데 틀렷다.

그래서 불을 먼저 퍼트리고 상근이를 이동시켯는데 맞았다....예외 케이스가 생각이 안 난다..

그리고!!!! 탈출과 불 문제의 차이점이 하나가 있는데

탈출은 다음에 물이 찰 곳으로 이동을 못 하며

불은 다음에 불이 와도 바로 이동이 가능하여 불이 올 곳으로도 이동이 가능하다는 것이다.

제출코드

#include <stdio.h>
#include <string.h>
int T, w, h, fire_front = -1, fire_back=-1, S_front=-1, S_back=-1, fire_Q[1000000][2], S_Q[100000][2], D[200000];
int dx[4] = { -1,0,0,1 }, dy[4] = { 0,-1,1,0 },fire_c=0,S_c=0;
int arr[1010][1010];
 
void reset();
void input();
 
int main()
{
    scanf("%d",&T);
 
    while (T--)
    {
        int count = 0;
        int flag = 0;
        reset();
        input();
        while (S_front!=S_back||fire_front!=fire_back)//불 한 단계동안 BFS
        {
            for (int i = 0; i < fire_c; i++)
            {
                fire_front++;
                for (int j = 0; j < 4; j++)
                {
                    int fire_h = fire_Q[fire_front][0] + dy[j];
                    int fire_w = fire_Q[fire_front][1] + dx[j];
                    if ((arr[fire_h][fire_w] == '.' || arr[fire_h][fire_w] == 1) && arr[fire_h][fire_w] != '*')
                    {
                        arr[fire_h][fire_w] = '*';
                        fire_Q[++fire_back][0] = fire_h;
                        fire_Q[fire_back][1] = fire_w;
                        count++;
                    }
                }
            }
            fire_c = count;
            count = 0;
 
            count = 0;
            for (int i = 0; i < S_c; i++)//상근이 한 단계 동안 BFS
            {
                S_front++;
                for (int j = 0; j < 4; j++)
                {
                    int S_h = S_Q[S_front][0] + dy[j];
                    int S_w = S_Q[S_front][1] + dx[j];
                    if (arr[S_h][S_w]=='.')
                    {
                        arr[S_h][S_w] = 1;
                        S_Q[++S_back][0] = S_h;
                        S_Q[S_back][1] = S_w;
                        D[S_back] = D[S_front] + 1;
                        count++;
                    }
 
                    if (arr[S_h][S_w] == 0)
                    {
                        printf("%d\n",D[S_front]+1);
                        flag = 1;
                        break;
                    }
 
                }
                if (flag == 1)     break;
            }
            S_c = count;
            count = 0;
 
            if (flag == 1) break;
 
        }
        if(flag==0)
            printf("IMPOSSIBLE\n");
    }
 
    return 0;
}
 
void reset()//초기화
{
    memset(arr, 0, sizeof(arr));//지도
    memset(fire_Q, 0, sizeof(fire_Q));//불의 큐
    memset(S_Q, 0, sizeof(S_Q));//상근이 큐
    memset(D, 0, sizeof(D));//몇 칸 움직였는지
    S_back = -1;//상근이 백
    S_front = -1;//상근이 프론트
    fire_back = -1;//불 백
    fire_front = -1;//불 프론트
    fire_c = 0;//불의 BFS에서 한 단계에서 몇 번 반복해야되는지
    S_c = 0;//불의 BFS에서 한 단계에서 몇 번 반복해야되는지
}
 
void input()//입력
{
    scanf("%d %d",&w,&h);
    getchar();
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            scanf("%c",&arr[i][j]);
 
            if (arr[i][j]=='*')
            {
                fire_Q[++fire_back][0] = i;
                fire_Q[fire_back][1] = j;
                fire_c++;
            }
            else if (arr[i][j]=='@')
            {
 
                arr[i][j] = 1;
                S_Q[++S_back][0] = i;
                S_Q[S_back][1] = j;
                S_c++;
            }
        }
        getchar();
    }
}

#백준 #알고리즘 #BFS #5427불