[BOJ] 6593: 상범 빌딩

문제 링크

Question

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

Input

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

Output

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

 

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

---

Solution

2차원 미로에서 출구까지 걸리는 최단 거리를 찾는 것에, 차원이 1개 더 추가된 형태이다.
따라서 시작 지점부터 미로를 순회하면서 탈출구에 도달했다면 해당 탈출구까지의 거리를 반환하고, 더 이상 방문할 지점이 없다면 탈출 불가능을 반환하면 된다.

while queue:
    cur_i, cur_j, cur_k, dist = queue.popleft()
    if board[cur_i][cur_j][cur_k] == 'E':
        return dist

    for di, dj, dk in [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)]:
        next_i = cur_i + di
        next_j = cur_j + dj
        next_k = cur_k + dk

        if not (0<=next_i<L and 0<=next_j<R and 0<=next_k<C):
            continue
        if board[next_i][next_j][next_k] == '#':
            continue
        if visited[next_i][next_j][next_k]:
            continue

        visited[next_i][next_j][next_k] = True
        queue.append((next_i, next_j, next_k, dist+1))

Queue에는 현재 좌표와 해당 지점까지의 최소 거리가 저장된다. 각 6방향의 움직임에서

1. 움직일 좌표가 이동 가능한 좌표인지,
2. 해당 좌표가 지나갈 수 있는 칸인지,
3. 해당 좌표를 방문한 적이 있는지

를 확인한 후, 해당 좌표와 이동 거리(=현재 거리 + 1)를 Queue에 저장한다.

 

이때, 현재 좌표의 값이 E라면 해당 좌표까지의 거리가 탈출하는 최단 거리이고, Queue가 텅 빌때까지 탈출하지 못한다면 이는 탈출 불가능한 것이므로 -1을 반환하도록 한다.

 

전체 정답 코드는 아래와 같다.

import sys
from typing import List, Tuple
from collections import deque
input = lambda: sys.stdin.readline().strip()

def bfs(board: List[List[str]], size: Tuple[int, int, int], start_point: Tuple[int, int, int]):
    L, R, C = size
    s_i, s_j, s_k = start_point

    visited = [[[False]*C for _ in range(R)] for _ in range(L)]
    visited[s_i][s_j][s_k] = True
    queue = deque([(*start_point, 0)])

    while queue:
        cur_i, cur_j, cur_k, dist = queue.popleft()
        if board[cur_i][cur_j][cur_k] == 'E':
            return dist

        for di, dj, dk in [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)]:
            next_i = cur_i + di
            next_j = cur_j + dj
            next_k = cur_k + dk

            if not (0<=next_i<L and 0<=next_j<R and 0<=next_k<C):
                continue
            if board[next_i][next_j][next_k] == '#':
                continue
            if visited[next_i][next_j][next_k]:
                continue

            visited[next_i][next_j][next_k] = True
            queue.append((next_i, next_j, next_k, dist+1))

    return -1


def solution(L: int, R: int, C: int, board: List[List[str]]):
    for i in range(L):
        for j in range(R):
            for k in range(C):
                if board[i][j][k] == 'S':
                    return bfs(board, (L, R, C), (i, j, k))


if __name__ == "__main__":
    while True:
        L, R, C = list(map(int, input().split()))
        if L==0 and R==0 and C==0:
            break

        board = []
        for _ in range(L):
            floor = [input() for _ in range(R)]
            board.append(floor)
            input()

        answer = solution(L, R, C, board)
        if answer >= 0:
            print(f"Escaped in {answer} minute(s).")
        else:
            print("Trapped!")