[BOJ] 백준 6593 상범 빌딩

출처: https://www.acmicpc.net/problem/6593

 Input 

3 4 5

S....

.###.

.##..

###.#

 

#####

#####

##.##

##...

 

#####

#####

#.###

####E

 

1 3 3

S##

#E#

###

 

0 0 0

 

 Output 

Escaped in 11 minute(s).

Trapped!

- 전형적인 (2차원) BFS 문제에서 3차원으로 확장한 문제입니다.

- map과 visited를 [층 h][행 x][열 y]로 표시해서 3중 for문을 이용해서 입력을 받습니다.

- BFS 탐색시에는 범위 초과(높이, 행, 열), 벽을 만난 경우, 보다 좋은 비용이 아닌 경우를 제외하고 탐색합니다.

※ Test Case가 존재하므로 초기화에 유의

---

#include <stdio.h>
 
inline int min(int A, int B) { if (A < B) return A; return B; }
const int dx[] = {0, 0, -1, 1, 0, 0};
const int dy[] = {-1, 1, 0, 0, 0, 0};
const int dz[] = {0, 0, 0, 0, -1, 1};
const int MAX_LRC = 30 + 5;
const int INF = 2e9;
char map[MAX_LRC][MAX_LRC][MAX_LRC];
int visited[MAX_LRC][MAX_LRC][MAX_LRC];
struct Node {
    int h, x, y, cost;
}start, que[MAX_LRC * MAX_LRC * MAX_LRC * 6];
int L, R, C, ans;
int fr, re;
 
void init() {
    for (int k = 0; k < L; ++k) {
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                visited[k][i][j] = INF;
            }
        }
    }
    // 큐 초기화
    fr = re = 0;
    // 정답 초기화
    ans = INF;
}
 
void BFS() {
    // 시작 지점
    que[re++] = start;
    visited[start.h][start.x][start.y] = start.cost;
 
    while (fr < re) {
        Node cur = que[fr++];
 
        // 도착한 경우 최소비용으로 갱신
        if (map[cur.h][cur.x][cur.y] == 'E') {
            ans = min(ans, cur.cost);
            continue;
        }
 
        for (int i = 0; i < 6; ++i) {
            int nextH = cur.h + dz[i];
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
 
            // 범위를 벗어나는 경우
            if (nextH < 0 || nextH >= L ||
                nextX < 0 || nextX >= R ||
                nextY < 0 || nextY >= C)
                continue;
 
            // 벽을 만난 경우
            if (map[nextH][nextX][nextY] == '#')
                continue;
 
            // 보다 좋은 비용으로 방문한 경우만 허용
            int nextCost = cur.cost + 1;
            if (visited[nextH][nextX][nextY] <= nextCost)
                continue;
            
            visited[nextH][nextX][nextY] = nextCost;
            que[re++] = { nextH, nextX, nextY, nextCost };
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    while (1) {
        scanf("%d %d %d", &L, &R, &C);
        if (L == 0 && R == 0 && C == 0)
            break;
 
        init();
        for (int k = 0; k < L; ++k) {
            for (int i = 0; i < R; ++i) {
                scanf("%s", map[k][i]);
                for (int j = 0; j < C; ++j) {
                    if (map[k][i][j] == 'S') {
                        start.h = k;
                        start.x = i;
                        start.y = j;
                        start.cost = 0;
                    }
                }
            }
            scanf("");
        }
 
        BFS();
 
        if (ans == INF) printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n", ans);
    }
}