개요
🖱️ 문제 링크 : https://www.acmicpc.net/problem/3055
- 시간 제한 : 1초
- 메모리 제한 : 128 MB
- 기출 : Contest > Croatian Open Competition in informatics > COCI 2006/2007 > Contest #1 4번
문제
⌨️ 입력
첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.
🖨️ 출력
첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.
해결 방법
💡 문제 이해
'불' 문제와 매우 유사하다!
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
이 말이 무슨 말인지 이젠 바로 이해가 된다.
물이 찰 예정인 칸으로는 이동이 안된다 = 물 차오름 -> 고슴도치 이동 -> 물 차오름 순서로 구현
익숙한 유형이 보이니 이젠 반갑다!
미리 물이 차 있는 지역을 'water' 큐에 담아준다.
그리고 사이클이 돌기전 큐의 길이 만큼만 반복문을 돌려주며 물 차오름 -> 고슴도치 이동 -> 물 차오름 .. 을 구현한다.
flood 함수로 인접한 칸들에 물이 차오르게 한다음, escape 함수로 고슴도치를 이동 시킨다.
고슴도치가 열심히 이동하다가, 'D'(비버의 굴)에 도달하게 되면 해당 최소 비용을 출력한 뒤 종료한다.
Python Code
# 백준 3055 탈출
import sys
from collections import deque
read = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
queue = deque()
water = deque()
def flood():
len_water = len(water)
for _ in range(len_water):
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:
# 이동한 위치가 빈 공간인 경우
if forest[nx][ny] == '.':
forest[nx][ny] = '*'
water.append([nx,ny])
def escape():
while queue:
len_q = len(queue)
for _ in range(len_q):
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if forest[nx][ny] == '.' and visited[nx][ny] == 0:
queue.append([nx,ny])
visited[nx][ny] = visited[x][y] + 1
elif forest[nx][ny] == 'D' and visited[nx][ny] == 0:
print(visited[x][y] + 1)
return
flood()
print("KAKTUS")
return
# R행 C열
R,C = map(int,read().split())
# '.' : 비어있는 곳
# '*' : 물이 차있는 곳
# 'X' : 돌
# 'D' : 비버의 굴
# 'S' : 고슴도치 위치
forest = [ list(map(str,read().rstrip())) for _ in range(R) ]
visited = [ [0]*C for _ in range(R) ]
for i in range(R):
for j in range(C):
if forest[i][j] == 'S':
queue.append([i,j])
forest[i][j] = '.'
elif forest[i][j] == '*':
water.append([i,j])
flood()
escape()
달려