[BOJ] [Python] 6593번 : 상범 빌딩

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

6593번: 상범 빌딩

문제

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

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

 

입력

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

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

 

출력

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

Escaped in x minute(s).

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

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

Trapped!

 

풀이방법

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

7569번: 토마토

 

이 문제와 비슷하게 풀면 됩니다.

dx, dy 뿐만 아니라 dz 까지 추가해서 동, 서, 남, 북, 상, 하까지 6가지 방법으로 BFS를 사용해서 출구를 찾으면 됩니다. 대신에 출구를 찾지 못하면 Trapped!를 출력하면됩니다.

 

 

코드

import sys
from collections import deque

input = sys.stdin.readline

dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

def bfs():
    while s:
        item = s.popleft()
        z, x, y, cnt = item
        if E[0] == x and E[1] == y and E[2] == z:
            return cnt
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
                if not visited[nz][nx][ny] and (matrix[nz][nx][ny] == '.' or matrix[nz][nx][ny] == 'E'):
                    visited[nz][nx][ny] = True
                    s.append([nz, nx, ny, cnt + 1])

    return -1


while True:
    h, n, m = map(int ,input().rstrip().split())
    matrix = []
    if h == n == m == 0:
        break

    # 행렬 입력
    for __ in range(h):
        if __ > 0:
            input()
        temp = [list(list(input().rstrip())) for _ in range(n)]
        matrix.append(temp)

    visited = [[[False] * m for _ in range(n)] for __ in range(h)]

    s = deque([])

    roof = False
    for k in range(h):
        for i in range(n):
            for j in range(m):
                if matrix[k][i][j] == 'S':
                    s.append([k,i,j,0])
                    visited[k][i][j] = True
                if matrix[k][i][j] == 'E':
                    E = [i,j,k]

    # s 위치 찾기
    result = bfs()

    if result == -1:
        print("Trapped!")
    else:
        print(f"Escaped in {result} minute(s).")
    input()