🥇 6593 상범 빌딩
문제
상범 빌딩은 각 변의 길이가 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차원 문제와 유사하다. 골드 티어 문제였지만 논리 자체는 bfs 기본 예제였기 때문에 어렵지 않게 풀었다.
출발 지점과 탈출 지점이 항상 하나만 존재한다 했으므로 따로 좌표를 찾아 저장해둔다. 큐에는 출발 지점 좌표를 넣어 출발 지점으로부터 위, 아래, 상하좌우로 이동할 수 있도록 했다. 벽을 제외한 공간을 이동하게 두었고 이동할 때마다 visited 배열의 값을 전에 있던 칸 +1을 해주었다. 마지막으로 방문한 칸이 E이면 전에 있던 칸의 값을 그대로 넣어주어 출력해주었다. 만약 값이 0이되면 방문할 수 없는 칸이 되므로 탈출 불가라 볼 수 있다. 따라서 0 인경우는 Trapped!를 출력해 주었다.
소스 코드
import sys
from collections import deque
input = sys.stdin.readline
while True:
l, r, c = map(int, input().split())
if l == 0 and r == 0 and c == 0:
break
board = []
start_d, start_x, start_y = -1, -1, -1
end_d, end_x, end_y = -1, -1, -1
for _ in range(l):
tmp = [list(input().strip()) for _ in range(r)]
board.append(tmp)
input()
# S : 시작 지점, E : 탈출 지점
# . : 빈 칸, # : 벽
for i in range(l):
for j in range(r):
for k in range(c):
if board[i][j][k] == 'S':
start_d, start_x, start_y = i, j, k
elif board[i][j][k] == 'E':
end_d, end_x, end_y = i, j, k
q = deque([(start_d, start_x, start_y)])
visited = [[[0 for _ in range(c)] for _ in range(r)] for _ in range(l)]
visited[start_d][start_x][start_y] = 1
while q:
depth, x, y = q.popleft()
for nd, nx, ny in (depth - 1, x, y), (depth + 1, x, y), (depth, x + 1, y), (depth, x - 1, y), (depth, x, y - 1), (depth, x, y + 1):
if nx < 0 or ny < 0 or nd < 0 or nx >= r or ny >= c or nd >= l:
continue
if board[nd][nx][ny] == 'E':
visited[nd][nx][ny] = visited[depth][x][y]
break
elif not visited[nd][nx][ny] and board[nd][nx][ny] != '#':
visited[nd][nx][ny] = visited[depth][x][y] + 1
q.append((nd, nx, ny))
res = visited[end_d][end_x][end_y]
if res != 0:
print(f"Escaped in {res} minute(s).")
else:
print("Trapped!")
