🔴 문제 개요
🚀 난이도 : GOLD 4
R X C matrix에서 고슴도치의 위치(시작점) -> 비버의 굴(도착점) 까지 홍수와 벽을 피해 갈 수 있는 최단 시간을 구하는 문제. 매분 물이 퍼지고, 고슴도치는 분마다 한 칸씩 이동 가능하다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
제한사항
- 50보다 작거나 같은 자연수 R과 C가 주어진다.
- 'D'와 'S'는 하나씩만 주어진다.
🟠 Solution
입력의 범위가 매우 작기에, 부담없이 그래프 탐색을 활용한 구현 문제로 생각하고 문제를 풀이할 수 있을 것 같습니다. 주의할 점은 마지막 설명 부분 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다 입니다.
이를 위해서 우리는 특정 칸에 언제 물이 차는 지를 알아둘 필요가 있습니다. 고슴도치가 이동할 때 그 부분에 물이 차 있는지를 알아야 이동할 수 있는지 없는지를 판단할 수 있겠죠. 따라서 고슴도치의 이동 전 물의 이동을 먼저 계산하여 표시하도록 하는 전략을 취해보겠습니다.
먼저 입력부입니다.
import sys
from collections import deque
from typing import Tuple, Union
input = sys.stdin.readline
# input
R, C = map(int, input().rstrip().split())
matrix = []
# 물의 이동을 담을 큐
flood_queue = deque()
for r in range(R):
row = input().rstrip()
for c, v in enumerate(row):
if v == "D":
en = (r, c, 0)
elif v == "S":
st = (r, c, 0)
elif v == "*":
flood_queue.append((r, c, 0))
matrix.append(list(row))고슴도치 위치(S), 비버의 굴 위치 (D), 물의 초기 위치(*)를 잘 파악할 수 있도록 입력을 받아야 합니다. (r, c, 0) 처럼 큐에 담을 좌표 이외에 넣어주는 0은 해당 좌표를 큐에서 꺼냈을 때 시간을 파악하기 위함입니다.
먼저 홍수를 일으켜 물이 특정 칸에 도달하는 시간을 matrix에 표시해놓겠습니다. 입력부에서 큐에 넣어놓은 물의 시작점들을 기준으로 네 방향으로 이동하게 됩니다.
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def flood() -> None:
"""
홍수를 발생시켜 matrix의 (y, x) 위치에 물이 이동하는 시간을 표시한다.
"""
while flood_queue:
y, x, cnt = flood_queue.popleft()
if cnt == 0:
matrix[y][x] = 0
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if 0 <= ny < R and 0 <= nx < C and matrix[ny][nx] == ".":
matrix[ny][nx] = cnt + 1
flood_queue.append((ny, nx, cnt + 1))현재 matrix의 특정 지점의 값은 그 지점에 물이 닿았다면, 물이 닿은 시간이 표시되어 있습니다. 반대로 물이 닿지 않는 경우는 그대로 .가 표시되어있음에 주의해야 합니다.
다음은 실제 고슴도치를 이동시켜 비버의 굴까지 갈 수 있는 최단 시간을 구해보겠습니다.
def move(st: Tuple[int, int, int]) -> Union[int, str]:
"""
고슴도치가 (y, x)위치에 물이 차기 전 이동하여 굴까지 가는 최소시간을 반환한다.
"""
queue = deque([st])
while queue:
y, x, cnt = queue.popleft()
if cnt == 0:
matrix[y][x] = "X"
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if 0 <= ny < R and 0 <= nx < C and matrix[ny][nx] != "X":
if matrix[ny][nx] == "D": # 다음 좌표가 굴인 경우
return cnt + 1
# 물이 없는 지역이거나, 다음 이동 시간에 물이 차지 않는 경우에만 이동
if matrix[ny][nx] == "." or cnt + 1 < matrix[ny][nx]:
queue.append((ny, nx, cnt + 1))
matrix[ny][nx] = "X"
return "KAKTUS" # 이동 실패시
flood()
print(move(st))그래프 탐색은 BFS로 구현했습니다. 벽을 피해 4 방향 탐색 시, 다음 좌표가 비버의 굴인 경우 탈출에 성공할 수 있다는 것이므로 현재 cnt에 +1을 하여 반환합니다.
고슴도치가 다음에 이동하고자 하는 지점에 물이 차있더라도 다음 시간(cnt+1)이 matrix에 표시되어있는 시간보다 작다면 이동 가능합니다. 해당 시간에는 아직 물이 차지 않는 시간이니까요. 물이 차있지 않는 지점(.)이라면 그냥 이동해주면 됩니다. 고슴도치 이동 후에는 해당 위치 값을 벽(X)으로 표시하여 방문처리를 해주었습니다.
최종적으로 프로그램의 메인 부에서 두 메서드들을 순차적으로 실행하여 문제를 마무리했습니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
