[Jungol] 정올 1082 화염에서탈출(SLIKAR)

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=50

Approach

동시다발적으로 확장되는 불을 피해서 용사는 집(D)에 도착하여야 합니다.

① 각각의 불이 퍼지는 시간을 timeMap[][]에 저장합니다. ← BFS

[Test Case 1]

[Test Case 2]

- timeMap[][] = 0인 곳은 바위이거나 불이 시작했던 위치

- timeMap[][] = 0이 아닌 숫자는 불이 번지는 시점

  ex) timeMap[5][1] = 10초에 해당 지점에 불 존재.

② 용사가 이동할 때 바위가 있는 곳이거나 그 시점에 불이 번지는 곳을 피하며 이동합니다. ← BFS

▶ 즉, 불에 대한 BFS를 먼저 처리한 후, 용사에 대한 BFS 처리

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 55;
const int INF = LM * LM;
int N, M, timeMap[LM][LM];
int startX, startY, endX, endY;
int fr, re;
int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };
 
struct Queue {
    int r, c, lev;
} que[INF];
 
void push(int r, int c, int lev) {
    // 불의 경우: 바위나 도착점의 경우는 0으로 표시되어 침범 X
    // 재우(용사)의 경우 바위만 0으로 표시되어 갈 수 없음.
    if (timeMap[r][c] <= lev) return;
    timeMap[r][c] = lev;
    que[re++] = { r, c, lev };
}
 
void input() {
    int i, j;
    char ch;
    scanf("%d %d", &N, &M);
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= M; j++) {
            scanf(" %c", &ch);
            timeMap[i][j] = INF;
            if (ch == 'X') // 바위
                timeMap[i][j] = 0;
            else if (ch == 'S') // 재우의 처음 위치
                startX = i, startY = j;
            else if (ch == '*') // 불
                push(i, j, 0);
            else if (ch == 'D') // 용사의 집(도착점)
                endX = i, endY = j;
        }
    }
}
 
void BFS() {
    Queue t;
    // Queue가 비워질 때까지
    while (fr < re) {
        t = que[fr++];
        for (int i = 0; i < 4; i++)
            push(t.r + dr[i], t.c + dc[i], t.lev + 1);
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
 
    // 불의 경우 도착점에 갈 수 없도록 설정
    timeMap[endX][endY] = 0;
    BFS(); // 불부터 시간대별로 확장 표시
 
    fr = re = 0;
    // 용사는 도착점을 갈 수 있는 곳으로 설정
    timeMap[endX][endY] = INF;
    push(startX, startY, 0);
    BFS();
 
    // 용사가 성공적으로 목적지에 도달한 경우
    if (timeMap[endX][endY] < INF)
        printf("%d\n", timeMap[endX][endY]);
    else puts("impossible");
}