문제 보러 가기
문제
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.
당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?
입력
입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.
그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.
출력
각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.
Escaped in x minute(s).
여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.
만일 탈출이 불가능하다면, 다음과 같이 출력한다.
Trapped!
예제 입력 1
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
예제 출력 1
Escaped in 11 minute(s).
Trapped!
우선 입력받는게 어려웠다. 처음보는 유형의 입력방식이라 결국 인터넷 찬스를 사용하여 푼 문제가 되었다.
그것외에는 위, 아래로 이동가능한 BFS문제로 이전에 토마토 문제 와 또 비슷한거 같다.
이전에는 BFS를 인프런 강의인 파이썬 알고리즘 문제풀이 입문 에서 배운것처럼 폼을 유지하려 했으나 어떤 조건을 만족할때 바로 while문을 벗어나기 위해서 함수화 하는것이 맞는거 같다.
따라서 나도 BFS문제를 함수화하기로 하였다.
import sys
from collections import deque
# 이런 유형은 결국 return으로 while문을 탈출하기 위해 BFS 함수화 하는것이 맞는듯
sys.stdin=open('input.txt', 'r')
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
def BFS(l,r,c):
Q.append([l,r,c])
dis[l][r][c]=1
while Q:
x,y,z=Q.popleft()
for i in range(6):
nx=x+dx[i]
ny=y+dy[i]
nz=z+dz[i]
if 0<=nx<L and 0<=ny<R and 0<=nz<C:
if board[nx][ny][nz]=='E':
print("Escaped in {} minute(s).".format(dis[x][y][z]))
return
if board[nx][ny][nz]=='.' and dis[nx][ny][nz]==0:
dis[nx][ny][nz] = dis[x][y][z]+1
Q.append([nx,ny,nz])
print('Trapped!')
if __name__=="__main__":
while True:
L,R,C=map(int, input().split()) # L, R, C : 층, 행, 열
if L==0 and R==0 and C==0:
break
board = [[[]*C for _ in range(R)] for _ in range(L)] # 빈 리스트 만들기
dis = [[[0]*C for _ in range(R)] for _ in range(L)]
Q = deque()
for l in range(L):
board[l]=[list(map(str, input().strip())) for _ in range(R)] # 각 층별 정보 넣기
input() # 빈 줄을 위해 !!!!!!
for l in range(L):
for r in range(R):
for c in range(C):
if board[l][r][c]=='S': # 시작시점을 찾고 시작시점에서 BFS 시작
# BFS 시작
BFS(l,r,c)
