BOJ 6593 - 상범 빌딩

문제

백준 온라인 저지 - 6593번

풀이 과정

시작 지점에서 목표 지점에 도달하기 위한 최단 거리를 구하는 BFS 문제입니다.
빌딩이 3차원이기 때문에 상태공간을 다음과 같이 정의해줍니다.

visit[z][x][y] = z 층의 (x, y) 지점에 방문했는지 유무를 저장

여기서 z 축 을 첫번째 인덱스로 지정한 것은 구현상의 편의를 위한 것입니다.
각 지점들을 방문할 때 동서남북 및 위층, 아래층 까지 같이 탐색을 수행하며 도달 여부를 판단해주면 됩니다.

코드

import sys
from collections import deque

L, R, C = 0, 0, 0
building = []


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


def bfs(start):
    q = deque()
    visit = [[[0] * C for _ in range(R)] for _ in range(L)]

    q.append([start[0], start[1], start[2], 0])
    visit[start[0]][start[1]][start[2]] = 1

    while q:
        z, x, y, cost = q.popleft()

        if building[z][x][y] == 'E':
            return cost

        # 동서남북 이동
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if not visit[z][nx][ny] and building[z][nx][ny] != '#':
                    visit[z][nx][ny] = 1
                    q.append([z, nx, ny, cost + 1])

        # 상하 이동
        for i in range(2):
            nz = z + dz[i]
            if 0 <= nz < L:
                if not visit[nz][x][y] and building[nz][x][y] != '#':
                    visit[nz][x][y] = 1
                    q.append([nz, x, y, cost + 1])

    return -1


def solution():
    start = []

    # 시작지점 찾기
    for z in range(L):
        for x in range(R):
            for y in range(C):
                if building[z][x][y] == 'S':
                    start = [z, x, y]

    return bfs(start)


if __name__ == '__main__':
    while True:
        L, R, C = list(map(int, sys.stdin.readline().split()))
        if not L and not R and not C:
            break

        building = []
        for _ in range(L):
            building.append([list(sys.stdin.readline().strip()) for _ in range(R)])
            sys.stdin.readline()

        ans = solution()
        if ans != -1:
            print(f'Escaped in {ans} minute(s).')
        else:
            print('Trapped!')