상범 빌딩
문제
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 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!
정육면체를 코드로 어떻게 구현할까, 고민을 꽤 했던 문제였다.
3차원 리스트를 이용하면, x,y,z축 3개를 가진 좌표 평면을 구현할 수 있는 것을 볼 때, 3차원 리스트를 이용해보면 어떨까 싶었다.
3차원 리스트만 잘 구현해낸다면, 사실 문제 안에서 다뤄야할 부분은 4방향 탐색과 비슷한 유형의 문제이기 때문에 이후로는 조금의 실수 이외엔 무난하게 풀어냈다.
3차원 리스트 구현
result = [[[0]*C for _ in range(R)]for _ in range(L)]
graph = [[[]for _ in range(R)]for _ in range(L)]
visited = [[[False]*C for _ in range(R)]for _ in range(L)]방문처리할 요소, 거리 계산할 요소 모두, 3차원 배열로 만들어서, 일대일 대응이 되게끔 만들었다.
구현(BFS)
1.시작지점 S의 위치를 찾는다. S의 위치부터 BFS시작.
2.BFS할때, 4방향 탐색이 아닌, 6방향 탐색(동,서,남,북,상,하)을 하며, "."일 경우 큐에 좌표를 넣고, 반복
3.목적지 "E"까지 반복하며, 지나쳐온 거리를 더해가서, "E"에 도달하였을 때 해당 좌표의 거리 계산값 출력
import sys
from collections import deque
def bfs(c,a,b):
global result
global graph
global visited
queue = deque()
queue.append((c,a,b))
result[c][a][b] = 0
while queue:
c,a,b = queue.popleft() #왼쪽부터 뽑음 (왼쪽이 가장 먼저 들어간 정보)
for i in range(6): #6방향 탐색
x , y, z = a+dx[i],b+dy[i],c + dz[i]
if 0 <= x < R and 0 <= y < C and 0 <= z < L:
if graph[z][x][y] == "E":
print(f"Escaped in {result[c][a][b]+1} minute(s).")
return #f함수 활용
if not visited[z][x][y] and graph[z][x][y] == ".":
result[z][x][y] = result[c][a][b]+1
visited[z][x][y] = True
queue.append((z,x,y))
print("Trapped!")
while(1):
L,R,C = map(int,sys.stdin.readline().split())
if L+R+C ==0:
break
dx = [0,1,0,-1,0,0]
dy = [1,0,-1,0,0,0]
dz = [0,0,0,0,1,-1] #상하 축 좌표
result = [[[0]*C for _ in range(R)]for _ in range(L)]
graph = [[[]for _ in range(R)]for _ in range(L)]
visited = [[[False]*C for _ in range(R)]for _ in range(L)]
for i in range(L):
graph[i] = [list(map(str,sys.stdin.readline().rstrip()))for _ in range(R)]
sys.stdin.readline()
for z in range(L):
for x in range(R):
for y in range(C):
if graph[z][x][y] == "S":
bfs(z,x,y)3차원으로 접근한다는게 머리가 매우 아팠지만, 그래도 다른 탐색 문제와 비슷한 패턴을 보여주었기에, 풀 수 있었던 문제라고 생각한다.
