[백준] 6539 상범 빌딩 - 골드 5
[오늘의 문제]
https://www.acmicpc.net/problem/6593
[오늘의 학습 키워드]
- BFS, DFS
1. 문제 설명
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까?
상범 빌딩은 각 변의 길이가 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으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.
문제의 입력을 보면
이런식으로 입력이 주어집니다.
L, R, C 가 주어지며
L은 층 수, C는 한줄에 주어진 입력의 수, R은 줄의 수를 의미합니다.
입력의 마지막으로 0, 0, 0 이 주어집니다.
S에서 시작해 E로 이동이 가능하면 탈출에 걸린 시간을 출력하고 출력이 불가능 한 경우 trapped를 출력하면 됩니다.
[제한사항]
- 1 ≤ L, R, C ≤ 30
- R, C의 입력이 주어진 이후 공백 한줄이 주어진다.
- 이동은 '.' 으로만 이동이 가능하고 '#' 은 이동이 불가능 하다.
- 시작 지점과 출구는 항상 하나만 존재한다.
2. 접근방식
입력이 특이하게 주어지고 나머지는 BFS만 돌리면 되는 문제입니다.
그렇다면 주어진 입력을 제대로 받기 위해서는 특별한 방법을 사용해야 합니다.
우선 while문을 이용해 L, R, C가 0이 올때까지 입력받기를 반복해 줍니다.
L, R, C 를 입력받고 배열의 정보를 입력받아야 하는데
R, C를 입력받고 빈줄을 한번 입력받은 뒤 L 만큼 R, C를 입력을 받아야 합니다.
그러기 위해서 for 문을 이용해 L번 입력을 받는데 R만큼 또 반복을 실시하며 C줄을 입력받고 해당 줄을 모아주면 됩니다.
그렇게 구한 배열을 합쳐 3차원 배열로 만들어주고 동, 서, 남, 북, 상, 하 로 이동이 가능하도록 dx, dy, dz를 구성해 줍니다.
또 이동에 걸린 누적 시간을 구하기 위한 visited 배열을 만들어 주고 BFS 탐색을 실시해 종료 가능여부에 따라 출력 결과를 달리 해주면 됩니다.
3. 코드
import sys
from collections import deque
input = sys.stdin.readline
# 동, 서, 남, 북, 상, 하 -> 여기서 상, 하 는 층의 이동을 의미
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
# 입력받은 x, y, z 를 기준으로 출구 찾기
def BFS(x, y, z):
queue.append((x, y, z))
visited[x][y][z] = 1 # 현재 위치에서 출발 하니 1분으로 표시
# queue에 위치 정보 업데이트
while queue:
x, y, z = queue.popleft()
# 6방향 탐색
for k in range(6):
nx = x + dx[k]
ny = y + dy[k]
nz = z + dz[k]
# 배열의 범위를 벗어나지 않고 이동가능한 경로와 종료경우 찾기
if 0 <= nx < L and 0 <= ny < R and 0 <= nz < C:
# 다음칸으로 이동 가능한 경우 -> 중복 제거를 위해 visited가 0인 위치만 탐색
if buliding[nx][ny][nz] == '.' and visited[nx][ny][nz] == 0:
visited[nx][ny][nz] = visited[x][y][z] + 1
queue.append((nx, ny, nz))
# 종료조건 'E'를 만난 경우
elif buliding[nx][ny][nz] == 'E':
# 현재 걸린 시간을 출력
return print(f"Escaped in {visited[x][y][z]} minute(s).")
# BFS 탐색을 실시했는데 위의 return문을 만나지 못한 경우 -> 'E'를 만나지 못한 경우이므로 Trapped 반환
return print("Trapped!")
# 입력에 0, 0, 0이 들어와야 종료
while True:
L, R, C = map(int, input().split())
if L == 0 and R == 0 and C == 0:
break
buliding = [[[] for _ in range(R)] for _ in range(L)] # 입력받은 빌딩의 정보를 저장할 3차원 배열
visited = [[[0] * C for _ in range(R)] for _ in range(L)] # 해당 지점까지 걸린 시간을 저장할 visited 배열
queue = deque()
# 빌딩이 L층 존재
for i in range(L):
for j in range(R): # 줄마다 입력받고 building 배열에 업데이트
buliding[i][j] = list(input().strip())
input() # 공백 입력받기
# 3차원 배열을 탐색하며 시작지점 찾기
for i in range(L):
for j in range(R):
for k in range(C):
if buliding[i][j][k] == 'S':
BFS(i, j, k)[코드 설명]
입력을 받아줍니다.
while문을 이용해 무한 반복을 실시하는데 만약 L, R, C 가 0이 들어온다면 입력이 종료됩니다.
3차원 배열을 만들어 빌딩 정보를 저장하기 위해 building을 3차원 배열로 만들고 동일하게 visited 배열을 만들어 줍니다.
앞서 for문을 L번 반복하고 여기에 R번 반복을 실시해 한 줄씩 입력을 받고 그걸 building에 저장해 줍니다.
R번 입력을 다 받았으면 공백을 입력받기 위해 input을 하나 넣어줍니다.
이렇게 입력을 다 받았다면 BFS 탐색을 실시할 시작 위치를 찾아줍니다.
3중 반복문을 통해 'S'가 적힌 위치를 찾고 그 위치를 기준으로 BFS 탐색을 실시합니다.
BFS 탐색을 실시합니다.
그러기 위해 deque를 선언해 주고 dx, dy, dz를 생성해 줍니다.
입력받은 i, j, k 값을 기준으로 BFS 탐색을 실시할 것이고 시작 위치부터 1값을 가져야 도착 위치에 도착했을때 정상적으로 시간을출력 가능하니 현재 위치를 1로 업데이트 해줍니다.
queue에 시작위치를 넣고 while 문을 이용해 BFS 탐색을 실시합니다.
여기서 dx, dy, dz 의 길이가 6 이므로 6방향 탐색을 실시합니다.
또한 배열의 범위를 벗어나지 않았을 때 두가지 경우를 찾아줍니다.
1. 다음 칸으로 이동이 가능한 경우
2. 종료 위치로 이동이 가능한 경우
두 경우를 구분해 각각 코드로 작성해 주었습니다.
다음 위치로 이동이 가능하면 해당 위치를 queue에 넣어주고 visited를 업데이트 해줍니다.
누적값을 구하기 위해 현재값 + 1을 다음 위치에 업데이트 해줍니다.
도착 위치에 도착한 경우 시간을 출력해 줍니다.
여기서는 f-string 함수를 활용해 출력해 주었습니다.
while문이 종료되었는데 return에 걸리지 않았다는 것은 도착 위치에 도착하지 못했다는 의미로 trapped를 출력해주고 종료합니다.
4. 결과
[회고]
입력만 제대로 받는다면 무난하게 풀 수 있는 문제 였습니다.
입력 받을 때 3차원 배열을 생각하느냐 못하느냐의 차이 같습니다.
저의 경우 처음에는 2차원 배열로 입력을 받고 탐색이 종료된 경우 해당 위치를 반환하여 다음 2차원 배열의 시작 지점으로 사용하려 했으나 그렇게 구성하기도 복잡할 뿐더러 도착위치라는 개념이 존재하지 않아 입력의 방식을 바꾸어야 겠다고 생각하고 3차원 배열을 생각할 수 있었습니다.
만약 2차원 배열을 입력받고 다음 시작위치를 반환하는 경우 예제 1번의 경우 처음 1층은 잘 내려갈 지 몰라도 그 다음층에서는 탈출하는 방법이 복잡해져 포기한 방법입니다.
입력만 제대로 받고나니 단순 BFS만 실시하면 되는 문제 였습니다.
다음 시간에는 구현과 관련된 문제를 해결해 보겠습니다.