3055 - 탈출
문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
코드
from collections import deque
def spread(water):
len_w = len(water)
while len_w:
x, y = water.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] == '.':
graph[nx][ny] = '*'
water.append((nx, ny))
len_w -= 1
def move(i, j):
q = deque()
q.append((i, j))
visited[i][j] = 1
while q:
len_q = len(q)
while len_q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if graph[nx][ny] == '.' and not visited[nx][ny]:
visited[nx][ny] = visited[x][y] + 1
q.append((nx, ny))
elif graph[nx][ny] == 'D':
print(visited[x][y])
return
len_q -= 1
spread(water)
print("KAKTUS")
return
R, C = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
graph = [list(input()) for _ in range(R)]
visited = [[0] * C for _ in range(R)]
water = deque()
hog_x, hog_y = 0, 0
for i in range(R):
for j in range(C):
if graph[i][j] == 'S':
hog_x, hog_y = i, j
graph[i][j] = '.'
if graph[i][j] == '*':
water.append((i, j))
spread(water)
move(hog_x, hog_y)한마디
고슴도치는 물이 찰 예정인 곳으로 움직일 수 없기 때문에 물이 퍼지는 spread() 함수를 먼저 실행시킨 후에 고슴도치의 움직임을 나타내는 move() 함수가 실행되게끔 작성했다.
