📕문제

[Baekjoon] 6593. 상범 빌딩

문제 설명

정육면체 모양의 빌딩에서 출발지에서부터 시작해 도착지에 도착할 수 있는지, 가능하다면 걸리는 최단 거리를 구하는 문제다.

인접한 칸인 동, 서, 남, 북, 상, 하로만 움직일 수 있으며 일부 칸은 막혀있어 이동할 수 없다.

---

📝풀이

처음에 입력값을 받을 때 문제가 발생했다.

입력을 처리하는 코드

building = [[list(read().rstrip()) for _ in range(R)] for _ in range(L)]

• 3차원 배열을 사용해 floor[z][y][x] 형태로 입력을 받는다.
  여기서 z: 층, y: 세로, x: 가로

위 코드로 다음과 같은 예시를 입력했을 때

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1층은 정상이지만	2층부터 빈 배열이 생기더니	3층에도 생겼다.

왜 이런가 생각해봤더니 입력할 때 각 층을 구분하기 위해 한 줄을 비워놨기 때문이었다.

따라서 입력을 처리하는 코드를 다음과 같이 수정했다.

    building = []
    for _ in range(L):
        building.append([list(read().rstrip()) for _ in range(R)])
        read()

• 각 층에 대한 입력이 끝날 때마다 한 줄을 처리했다.

모든 층에 대한	입력이	잘 되었다.

문제를 풀기 전에 입력이 잘 되는지 확인하는 습관이 있어서 다행이었다.

이제 문제를 풀어보자.

아이디어는 시작점부터 BFS로 각 경로를 방문 표시를 하며 탐색하고 목적지에 도달하면 탐색을 중단하는 것이다.

여기서 조심해야 할게 그래프 탐색 문제라고 DFS로 접근하면 안된다는 것이다.
문제를 읽어보면 탈출 유무를 확인하는 것 뿐만 아니라 탈출에 걸리는 최단 시간, 즉 최단 거리를 출력으로 요구한다.
DFS로도 풀 순 있지만 첫번째로 찾은 경로가 가장 짧다는 보장이 없기 때문에 모든 경로에 대해 탐색을 진행해야 한다.
따라서 해당 문제는 DFS가 아닌 BFS로 풀어야한다!

import sys

read = sys.stdin.readline
from collections import deque

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

while(True):
    L, R, C = map(int, read().split())
    if L == 0 and R == 0 and C == 0:
        break

    building = []
    for _ in range(L):
        building.append([list(read().rstrip()) for _ in range(R)])
        read()

    visited = [[[False for _ in range(C)] for _ in range(R)] for _ in range(L)]
    
    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
                if building[z][y][x] == 'E':
                    end = (z, y, x)

    queue = deque([start])

    isEscaped = False
    while queue:
        z, y, x, count = queue.popleft()

        if (z, y, x) == end:
            isEscaped = True
            print(f'Escaped in {count} minute(s).')
            break

        for i in range(6):
            nz, ny, nx = z + dz[i], y + dy[i], x + dx[i]
            if 0 <= nz < L and 0 <= ny < R and 0 <= nx < C and not visited[nz][ny][nx]:
                if building[nz][ny][nx] != '#':
                    queue.append((nz, ny, nx, count + 1))
                    visited[nz][ny][nx] = True

    if not isEscaped:
        print('Trapped!')

• 건물 데이터를 building에 저장하고, 같은 크기의 visited에 방문 여부를 저장한다.
• 최초에 건물을 탐색해 시작점과 도착점 위치를 저장한다.
  시작점의 경우 해당 칸에 도달하기 위해 몇 번 이동했는지 저장하기 위한 변수를 추가한다. 또한 방문 표시를 하여 재방문이 이루어지지 않게 한다.
• 큐에 시작점을 넣은 후 탐색을 시작한다. 탐색은 큐가 비거나, 도착점에 도착했을 때 종료된다.
  • 큐에서 꺼낸 위치가 도착지인 경우 탐색을 종료한다.
  • 그렇지 않은 경우 이동할 수 있는 방향에 대한 칸을(범위에 벗어나지 않고 방문하지 않았을 때) 큐에 넣고 방문 표시를 한다.
    이 때 이동한 횟수를 증가시켜 해당 칸에 도달하기 위해 몇 번 움직였는지 기록한다.