[Python] 백준/BOJ 6593번: 상범 빌딩 (Gold 5)

💻 Problem

문제 보러 가기

 

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

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

 

💡 Approach

🙊 스스로 헷갈릴까 봐 쓰는 z, y, x 표기에 대한 주절주절..

나는 여태까지 행을 x 좌표, 열을 y 좌표로 표기해왔다.

사실 x축, y축으로 따지면 x 좌표가 열이고 y좌표가 행이라는 걸 알지만!

2차원 배열에 접근할 때 arr[y][x]로 표기하는 것이 어색하게 느껴져서 arr[x][y]로 표기하고자 그렇게 써왔다 

하지만 3차원 배열을 쓸 때 arr[z][x][y]로 표기하니까 이상한 거 같아서 이제 원칙대로 행을 y 좌표, 열을 x 좌표로 써야겠다..^_^

토마토 3차원 풀 때도 arr[z][x][y]로 표기했는데 이상하다 후

앞으론 x, y, z 축으로 맞게 써야짓!!

---

 

미로 찾기 3차원 버전이라고 생각하고 bfs로 풀면 된다!

빌딩 정보를 입력받은 후에 시작 지점을 찾는다.

시적 지점을 찾았다면 방문 처리하고 bfs ㄱㄱ

 

3차원이기에 6방향을 탐색한다.

나는 같은 층 기준 상하좌우, 위층, 아래층 순으로 6방향을 표기하는 게 편하다. (북남서동상하 순)

6방향을 탐색하며 다음 칸이 출구면 이동하여 탈출하고 비어있는 칸이면 이동해서 이어서 탐색하면 된다.

 

✏️ Solution

import sys
from collections import deque
input = sys.stdin.readline

# 북남서동상하
dz = (0, 0, 0, 0, -1, 1)
dy = (-1, 1, 0, 0, 0, 0)
dx = (0, 0, -1, 1, 0, 0)

def bfs(start):
    queue = deque([start])

    while queue:
        z, y, x, m = queue.popleft()

        # 6방향을 탐색한다
        for i in range(6):
            nz, ny, nx = z + dz[i], y + dy[i], x + dx[i]

            # 다음 위치가 범위를 벗어나거나 이미 방문한 칸이면 탐색하지 않는다
            if nz < 0 or nz >= l or ny < 0 or ny >= r or nx < 0 or nx >= c or visited[nz][ny][nx]:
                continue

            # 다음 칸이 출구면 탈출한다
            if building[nz][ny][nx] == 'E':
                print(f'Escaped in {m + 1} minute(s).')
                return

            # 다음 칸이 비어있는 칸이면 이동한다
            if building[nz][ny][nx] == '.':
                visited[nz][ny][nx] = True
                queue.append((nz, ny, nx, m + 1))
    
    print('Trapped!')

while True:
    l, r, c = map(int, input().split()) # 층 수, 행 개수, 열 개수
    
    if l == r == c == 0:
        break

    building = []
    visited = [[[False] * c for _ in range(r)] for _ in range(l)]

    # 빌딩의 칸 정보를 입력받는다
    for _ in range(l):
        building.append([list(input().rstrip()) for _ in range(r)])
        input()

    # 시작 지점 위치를 찾아서 저장한다
    start = None
    for z in range(l):
        for y in range(r):
            for x in range(c):
                if building[z][y][x] == 'S':
                    start = (z, y, x, 0)
                    visited[z][y][x] = True
                    bfs(start)
                    break

 

⏱️ 시간복잡도

• 총 시간복잡도는 O(l * r * c)이다.
  
  • 입력 처리: l * r * c
  • 시작 위치 탐색: l * r * c
  • bfs 탐색(정점의 개수 + 간선의 개수): l * r * c + 6 * l * r * c
  • 위의 세 가지를 더하면 9 * l * r * c이다.
• l, r, c 모두 최대 30이므로 최악의 경우 약 3 ^ 5 * 10 ^ 3 => 10 ^ 5이다.