[백준] 4179 불!

복기

이 전에 이와 비슷한 문제를 푼 적이 있었고 풀면 풀리겠다 생각했습니다. 

네... 방심을 했던거죠. 저의 전략은 이랬습니다.

일단, 불을 BFS로 먼저 퍼뜨립니다.

이 때, 맵의 각 칸에 언제 불이 도달하는지에 대한 값을 써넣습니다.

이후 지훈이를 큐에 넣고 똑같이 BFS를 돌립니다.

큐안에 들어간 지훈이는 현재의 시간값?!을 가졌기 때문에 주위 칸에 도착했을 때

이 칸이 이미 옛날 옛적에 불에 뒤덮힌 칸인지, 아직 불이 오지 않은 칸인지 알 수 있습니다.

사실 위와 같은 풀이는 방문 여부를 check하는 배열을 맵으로 대신해서 메모리를 아껴보고자 하는 욕심에서

비롯된 풀이였습니다만, 이때 저는 지훈이의 방문을 check하지 않는 실수를 범합니다.

지훈이가 시간 값을 가지기 때문에 불이 일찍이 덮친 칸들로 이동하지 못하고 (큐에 들어가지 못하고)

루프가 종료될 것으로 생각했습니다.

하지만, 불이 애초에 가지 못한 곳은 지훈이가 이동하면서 check해주지 않으면 영원히 0의 값을 가지게 됩니다.

큐가 터지게 되는거죠...

런타임 에러를 보고도 여기까지 생각하지 못하고 뭐지? 하며 황당했던 지난 날의 나를 용서합니다. ㅋ

결국 답답함을 이기지 못하고 다지우고 visit 배열을 사용해서 문제를 풀었고

다시 푸는 과정에서 위와 같은 케이스, 예를 들면, 5 5 에서

#	#	#	#	#
#	.	.	.	#
#	.	J	.	#
#	.	.	.	#
#	#	#	#	#

 

이와 같이 입력이 주어져 지훈이가 벽 안에서 계속 싸돌아 다니게 되는... 경우를 생각하게 됐습니다.

이후 지훈이의 방문 확인도 맵을 이용하면서 결국 visit 배열 메모리를 아껴서 문제를 다시 풀었습니다.

오기로 풀었습니다. ㅋㅋ

#include <stdio.h>
 
struct Crd { int x, y; };
int in[1010][1010];
Crd q[1000010];
int f, r;
int main(void) {
    int R, C, sx, sy, x, y, xx, yy, i, j;
    char ct;
    scanf("%d %d", &R, &C); getchar();
    for (i = 0; i < R; i++) {
        for (j = 0; j < C; j++) {
            ct = (char)getchar();
            if (ct == 'J') sx = i, sy = j;
            else if (ct == '#') in[i][j] = -1;
            else if (ct == 'F') in[i][j] = 1, q[r].x = i, q[r++].y = j;
        }
        getchar();
    }
 
    while (f < r) {
        x = q[f].x, y = q[f++].y;
 
        for (i = 0; i < 4; i++) {
            xx = x + "1210"[i] - '1';
            yy = y + "2101"[i] - '1';
 
            if (xx < 0 || R <= xx || yy < 0 || C <= yy || in[xx][yy]) continue;
            in[xx][yy] = in[x][y] + 1;
            q[r].x = xx, q[r++].y = yy;
        }
    }
 
    f = r = 0;
    q[r].x = sx, q[r++].y = sy;
    in[sx][sy] = 1;
    int ans = 0x7fffffff;
 
    while (f < r) {
        x = q[f].x, y = q[f++].y;
        if (x == 0 || y == 0 || x == R - 1 || y == C - 1) {
            ans = in[x][y];
            break;
        }
 
        for (i = 0; i < 4; i++) {
            xx = x + "1210"[i] - '1';
            yy = y + "2101"[i] - '1';
 
            if (xx < 0 || R <= xx || yy < 0 || C <= yy) continue;
            if (in[xx][yy] && in[xx][yy] <= in[x][y] + 1) continue;
            in[xx][yy] = in[x][y] + 1;
            q[r].x = xx, q[r++].y = yy;
        }
    }
 
    if (ans == 0x7fffffff) printf("IMPOSSIBLE");
    else                   printf("%d", ans);
    return 0;
}

복기 끝.