오늘의 알고리즘 boj-6593

문제

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

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

풀이

이 문제는 상하동서남북 이렇게 6군데의 방향을 잡는것, 3중리스트를 어떻게 초기화할지 그리고 높이, 행,열에 대한 개념만 잡혀있으면 기존의 BFS와 다를바가 없는 문제다.

3중 for문을 돌면서 start, end를 설정해주고 directions를 돌면서 상하동서남북을 각각 방문하면서 거리값을 업데이트 해준다.

마지막으로 queue의 제일 앞에 있는 값 그러니까 지금 조회하고 싶은 노드가 end와 같다면 현재 시간 값을 출력해주면 된다.

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


directions = [
        [1, 0, 0], [-1, 0, 0],
        [0, -1, 0],[0, 0, -1],
        [0, 1, 0], [0, 0, 1]
        ]

while True:
    L, R, C = map(int, input().split())
    if L == R == C == 0: break
    building = []
    for _ in range(L):
        building.append([input() for _ in range(R)])
        input()

    distances= [[[-1] * C for _ in range(R)] for _ in range(L)]

    for i in range(L):
        for j in range(R):
            for k in range(C):
                if building[i][j][k] == "S":
                    start = (i, j, k)
                    distances[i][j][k] = 0
                if building[i][j][k] == "E":
                    end = (i, j, k)


    queue = deque()
    queue.append(start)


    while queue:
        if queue[0] == end:
            time = distances[end[0]][end[1]][end[2]]
            print(f"Escaped in {time} minute(s).")
            break
        cur_height, cur_row, cur_col = queue.popleft()

        for direction in directions:
            next_height = cur_height+ direction[0]
            next_row = cur_row + direction[1]
            next_col = cur_col + direction[2]

            if next_height < 0 or next_height >= L or next_row < 0 or next_row >= R or\
                next_col < 0 or next_col >= C: continue
            if distances[next_height][next_row][next_col] != -1: continue
            if building[next_height][next_row][next_col] == "#": continue

            distances[next_height][next_row][next_col] = distances[cur_height][cur_row][cur_col] +1
            queue.append((next_height, next_row, next_col))
    else: print("Trapped!")