[파이썬/python] 백준 6593 - 상범빌딩

문제

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

---

문제 설명

1.   각 변의 길이가 1인 정육면체로 이루어져있는 상범 빌딩을 탈출해야 한다.
2. 각 칸에서 인접한 6칸(동, 서, 남, 북, 상, 하)으로 1분의 시간을 들여 이동할 수 있다.
3. 시작 지점(S)으로부터 출구(E)를 통해 탈출해야 한다.
   1. 탈출할 수 있다면 " Escaped in x minute(s)."를 출력한다.
   2. 탈출할 수 없다면 "Trapped!"를 출력한다.

 

---

문제에서 각 위치에서 다음 위치로 이동할 때 가중치가 1로 동일하다고 명시되어 있기에
BFS를 통해 3차원 배열을 탐색했다.

풀이

1. 입력받은 3차원 배열을 탐색하여 시작 지점(S)과 도착 지점(E)을 찾는다.
2.  시작지점부터 BFS탐색을 진행한다.
   1. 상, 하, 좌, 우, 위, 아래를 dx, dy, dz를 통해 표현하여 탐색한다.
      dz = [0,0,0,0,1,-1]
      dy = [0,1,0,-1,0,0]
      dx = [1,0,-1,0,0,0]
   2. queue에 z,y,x 좌표와 해당 위치까지의 거리 변수 dist를 같이 넣어 최단거리를 갱신한다.
   3. queue에서 꺼낸 좌표가 도착 지점이라면 현재까지의 거리 dist를 return한다.
3. 결과를 출력한다.

---

코드

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

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

def bfs(end):
    while queue:
        z,y,x,dist = queue.popleft()
        if (z,y,x) == end:
            return f'Escaped in {dist} minute(s).'
        for i in range(6):
            nz = z+dz[i]
            ny = y+dy[i]
            nx = x+dx[i]
            if nz < 0 or nz > L-1 or ny < 0 or ny > R-1 or nx < 0 or nx > C-1 or \
               visited[nz][ny][nx] or matrix[nz][ny][nx] == '#':
                continue
            queue.append((nz,ny,nx,dist+1))
            visited[nz][ny][nx] = 1
    return "Trapped!"

while True:
    L,R,C = map(int,input().split())
    if L == R == C == 0:
        break
        
    matrix = []
    for i in range(L):
        floor = [list(input().strip()) for _ in range(R)]
        input()
        matrix.append(floor)
    
    # 시작, 도착 지점 탐색
    for i in range(L):
        for j in range(R):
            for k in range(C):
                if matrix[i][j][k] == 'S':
                    start = (i,j,k,0)
                elif matrix[i][j][k] == 'E':
                    end =(i,j,k)
    
    queue = deque([])
    visited = [[[0 for _ in range(C)] for _ in range(R)] for _ in range(L)]
    visited[start[0]][start[1]][start[2]] = 1
    queue.append(start)

    ans = bfs(end)
    print(ans)

---

시간복잡도

• 최악의 경우 빌딩의 모든 좌표를 탐색하므로 시간복잡도는 $O(L*R*C)$이다.
• L,R,C는 최대 30이므로 약 $O(27000) = O(10^4)$의 시간복잡도를 가진다.