상범 빌딩

오늘도 역시 BFS문제를 가져왔다. BFS 기본 문제들에는 나름 자신감이 붙은 것 같다. 🔥

문제 분석

상범 빌딩에서 탈출하는 최소 시간을 구하고, 만약에 탈출을 못한다면, Trapped!를 출력하는 문제이다. 기본 BFS문제의 3차원 버전이라고 생각하면 된다.

다른 BFS문제와 달리 l,r,c에 0,0,0이 입력되기 전 까지 입력을 받고 출력하기를 반복해야 한다. 기존 BFS를 풀 때는 목표 지점까지 이동을 완료했을 때 sys.exit()을 통해 아얘 시스템을 종료해 버렸다. 하지만, 이 문제에서는 flag를 사용해 while 문을 탈출하고 다시 입력을 받는 과정을 반복하도록 했다.

예제 입력 1의 두번째 케이스처럼 이동할 수 없는 칸들에 둘러싸여 갇혔다면, point들에 새로운 요소들이 추가되지 않고 while문이 멈추게 됨으로 Trapped!를 출력한하게 된다.

보다 자세한 사항들은 코드에 주석으로 달아 놓았다.


CODE

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

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

while True:
    #0,0,0이 입력되기 전까지 계속 반복
    l,r,c=map(int,read().split())
    if l==0 and r==0 and c==0: break
    B=[]
    for _ in range(l):
        tmp=list(list(read().strip()) for _ in range(r))
        B.append(tmp)
        tmp=read()

    point=deque([])
    end_point=[]
    #시작점과 끝나는점 탐색
    for k in range(l):
        for i in range(r):
            for j in range(c):
                if B[k][i][j]=='S':
                    point.append([k,i,j])
                    B[k][i][j]=0
                elif B[k][i][j]=='E':
                    end_point=[k,i,j]
                    B[k][i][j]='.'
                    #끝나는 지점은 end_point에 따로 저장한 후에
                    #다른 이동가능한 점들과 똑같이 '.'으로 변경해준다.

    flag=2#도착지점에 도착했을 때 아래의 while문을 탈출하기 위한 flag
    while point:
        if flag==1:break
        a,b,q=point.popleft()
        for x,y,z in zip(dx,dy,dz):
            ax,by,qz=a+x,b+y,q+z
            if 0<=ax<l and 0<=by<r and 0<=qz<c and B[ax][by][qz]==".":
                point.append([ax,by,qz])
                B[ax][by][qz]=B[a][b][q]+1
                if [ax,by,qz]==end_point:
                    print('Escaped in ',B[ax][by][qz],' minute(s).',sep="")
                    flag=1
    #flag 가 그대로 2인 상태로 남아있다면 도착지점에 도착하지 못했다는 뜻이다.
    if flag==2: print('Trapped!')


[다시 풀어보기]