[백준] 6593번. 상범 빌딩

[백준] 6593번. 상범 빌딩 바로가기

아이디어

• 토마토 문제처럼 삼차원인 전형적인 bfs문제
• 테스트케이스가 여러개일 때 queue를 비우지 않아서 문제였다 -> 탈출 함수 지역 변수로 선언해서 해결했다(초기화)
• 그냥 return을 f스트링으로 받으면 된다. f스트링은 문자열로 바꿔주는 것

시간 복잡도

• O(L*R*C)

코드

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

# 탈출
def escape(start_f, start_r, start_c ):
        
    q = deque([(start_f, start_r, start_c, 0)])

    while q:
        f, r, c, time = q.popleft()

        # 동서남북
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]

            if 0 <= nr < R and 0 <= nc < C and not visited[f][nr][nc]: 
                # 탈출지점
                if building[f][nr][nc] == 'E':
                    return f'Escaped in {time + 1} minute(s).'

                if building[f][nr][nc] == '.':
                    q.append((f, nr, nc, time + 1))
                    visited[f][nr][nc] = 1

        # 상하
        for h in range(2):
            nf = f + df[h]

            if 0 <= nf < L and not visited[nf][r][c]:
                # 탈출지점
                if building[nf][r][c] == 'E':
                    return f'Escaped in {time + 1} minute(s).'

                if building[nf][r][c] == '.':
                    q.append((nf, r, c, time + 1))
                    visited[nf][r][c] = 1

    return "Trapped!"


df = [-1, 1]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

while True:
    L, R, C = map(int, input().split())
    # 종료조건
    if (L, R, C) == (0, 0, 0):
        break

    building = []
    visited = [[[0] * C for _ in range(R)] for _ in range(L)]
    start_f, start_r, start_c = 0, 0, 0


    # 층 입력받기
    for _ in range(L):
        floor = [list(input().strip()) for _ in range(R)]
        building.append(floor)
        input() # 각 층 사이에는 빈 줄이 있다


    # 상범이 위치 찾기
    for i in range(L):
        for j in range(R):
            for k in range(C):
                if building[i][j][k] == 'S':
                    start_f, start_r, start_c = i, j, k
                    break
        if (start_f, start_r, start_c) != (0, 0, 0): # 상범이 찾았으면 삼중 for문 탈출!
            break

    # 탈출하러가기
    print(escape(start_f, start_r, start_c))