[백준] 3055 : 탈출 - Python

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

내 코드 1

import sys
from collections import deque


n,m = map(int, input().split()) # ! 보드 칸
g = [list(map(str,input())) for _ in range(n)]

nowX,nowY = 0,0
endX,endY = 0,0
water = deque()
blank = "." # 이동 가능
wall = "X"  # 돌
w = "*"
des = "D"
for i in range(n):
    for j in range(m):
        if g[i][j] == "S":
            nowX,nowY = i,j
        if g[i][j] == "D":
            endX,endY = i,j
        if g[i][j] == "*": # 물
            water.append((i,j)) # 물 위치 저장

INF = int(1e9)
time = INF # ! 최단 시간 저장.
dx = [-1,0,1,0]
dy = [0,1,0,-1]

def isInner(x,y):
    if 0<=x<n and 0<=y<m:
        return True
    return False

dis = [[INF] * m for _ in range(n)]

def BFS(a,b): # ! 시작 지점.
    dq = deque()
    dq.append((a,b,0)) # 현재 위치, 현재 경로에서의 최단 시간 저장

    while len(dq) != 0 or len(water) != 0: # 여기서 조건을 or로 줘야만 했다. 이유는 둘 중 하나라도 된다면 계속 반복 돌아야해!!!!!
        # step1 : 물 먼저 확장
        size = len(water)
        for _ in range(size):
            x,y = water.popleft() # 해당 물 좌표는 결국 한번 확인하고 다시 확인할 필요가 없다.
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if isInner(nx,ny) and g[nx][ny] == blank: # 물이 확장하려는 좌표가 내부 좌표이면서 빈칸이라면
                    g[nx][ny] = w # 물로 채우기
                    water.append((nx,ny))
        # print("물 확장 후 보드 출력해보기 ")
        # printBoard()
        # step2 : 비버 이동 # 즉 비버 위치로부터 갱신
        size = len(dq)
        for _ in range(size):
            x,y,t = dq.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if isInner(nx,ny) and g[nx][ny] == blank: # ! 비버가 이동 가능한 경우
                    if t + 1 < dis[nx][ny]: # ! 최단거리 갱신 가능 하면 갱신
                        dis[nx][ny] = t+1
                        dq.append((nx,ny,t+1))
                elif isInner(nx,ny) and g[nx][ny] == des:
                    if t + 1 < dis[nx][ny]:
                        dis[nx][ny] = t + 1 # 여기서 뻗어나가면 안됨
        # print(f"비버 이동가능 좌표 갱신")
        # 갱신해야할 비버 좌표 지점 print(list(dq))
def printBoard():
    for i in range(n):
        for j in range(m):
            print(g[i][j], end = " ")
        print()

BFS(nowX, nowY)
if dis[endX][endY] == INF:
    print("KAKTUS")
else:
    print(dis[endX][endY])

코멘트1

처음 문제를 풀 때는 있는 그대로 구현하려고 했다. 문제에서 최소시간을 구하라고 했고, 좌표 기준으로 현재 경로의 시간이 갱신될 때마다 갱신하고 deque에 넣어주는 방식으로 풀었다.

근데 조건에서 물이 찰 예정인 곳에 비버가 갈 수 없다고 했기에 임의의 시간 t에 물이 먼저 이동하고, 비버가 움직이도록 했다.

그러려면 dq, water 둘 중 하나라도 존재한다면 계속 반복문을 돌고, 레벨 탐색으로 진행해야했다!!

• 즉 한번 사이클을 돌면 해당 갱신된 만큼만 돌면서 (즉 특정 t시간에 돌아야 하는 것들만 돌도록 진행)
  다익스트라를 구현했다.

for _ in range(size):
	x,y,t = dq.popleft()
    for i in range(4):
    	nx = x + dx[i]
        ny = y + dy[i]
        	if isInner(nx,ny) and g[nx][ny] == blank: # ! 비버가 이동 가능한 경우
            	if t + 1 < dis[nx][ny]: # ! 최단거리 갱신 가능 하면 갱신
                	dis[nx][ny] = t+1
                    dq.append((nx,ny,t+1))
                elif isInner(nx,ny) and g[nx][ny] == des:
                	if t + 1 < dis[nx][ny]:
                    	dis[nx][ny] = t + 1 # 여기서 뻗어나가면 안됨

위 코드의 핵심은 비버가 이동 가능한 곳(빈칸)인 경우 현재 경로의 시간이 기존 저장된 최단시간보다 작다면 최단거리고 갱신 -> 큐에 삽입 후 해당 좌표에서 다시 확인 진행

• 즉 다익스트라로 구현해야 한다.

또 elif isInner(nx,ny) and g[nx][ny] == des:
도착점에 도달하면 현재 경로의 시간이 기존 최단거리보다 작다면 -> 최단 거리 갱신

• 여기서 도착점에 도달한다면 큐에 삽입하지 않고 그냥 끝내 !

결국 조건들을 나열하면서 어떻게 풀어야 할 지 고민을 계속하자
1. 고슴도치가 비버의 굴로 이동하기 위해 필요한 최소 시간 구하기
1-1. 물이 모든 칸을 확산하는데 걸리는 시간 구하기
2. 고슴도치를 조건에 맞춰서 움직인다
2-1. 인접한 칸이 돌이 아닐 경우
2-2. 현재 이동한 시간과 해당 좌표 물이 차는데 걸리는 시간이랑 비교해서 아직 물이 차있는 칸이 아닌지 확인
2-3 최단거리 갱신 가능한지 확인

위 문제를 같은 방식이지만 좀 더 간결하게 생각하고 구현할 수 있다.

먼저 물에 대해서 먼저 BFS를 돌려서 해당 칸에 물이 몇초에 차는지 미리 기록
-> 이 과정은 기억하자 나중에 비슷한 유형을 만났을 때 똑같이 적용 가능!!
-> 트랩, 함정들이 존재하는 문제에서 새로운 배열을 만들어서 특정 좌표별로 해당 트랩이 발동하는 시간을 기록하자.
-> 이 문제처럼 물이 차오르는 시간을 따로 기록했다면
-> 현재 경로의 거리 기록하면서 이동한 좌표가 함정에 걸리지 않고(물이 차는 시간보다 빠르고) 기존 최단시간보다 빠른 시간이라면 최단시간 갱신 후 해당 좌표에서 다시 시작해야 하므로 값 넣어준다. (데크에 넣고 과정 반복)

내 코드2

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

n,m = map(int, input().split())
g = [list(map(str,input())) for _ in range(n)]

startX,startY = 0,0
endX,endY = 0,0
blank = "." # ! 빈칸
wall = "X" # ! 돌은 못 가
water = "*" # ! 물
des = "D"

waters = deque() # ! 물들의 좌표를 저장
water_time = [[1000] * m for _ in range(n)] # ! water_time[i][j] : (i,j) 좌표에 몇초에 물이 차는지 기록 : 즉 트랩 발동 시간
for i in range(n):
    for j in range(m):
        if g[i][j] == "S": # 시작점
            startX,startY = i,j
            g[i][j] = blank # ! 시작점은 빈칸으로 만들어야 함.
        if g[i][j] == "D": # 도착점
            endX,endY = i,j
        if g[i][j] == water:
            waters.append((i,j,0))
            water_time[i][j] = 0 # ! 시작하자마자 물이 시작되므로 해당 좌표는 안된다는 의미의 0

dx = [-1,0,1,0]
dy = [0,1,0,-1]

def isInner(x,y):
    if 0<=x<n and 0<=y<m:
        return True
    return False
def water_check():
    while waters:
        x,y,t = waters.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if isInner(nx,ny) and g[nx][ny] == blank: # ! 빈칸이면 물이 퍼질 수 있다
                if t + 1 < water_time[nx][ny]: # ! 기존 값보다 최신이라면 갱신
                    water_time[nx][ny] = t+1
                    waters.append((nx,ny,t+1))

water_check()
# for x in water_time:
#     print(x)
INF = int(1e9)
dis = [[INF] * m for _ in range(n)]

def BFS(a,b):
    dq = deque()
    dq.append((a,b,0)) #  ! 시작좌표, 현재 경로의 시간 기록

    while dq:
        x,y,t = dq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if isInner(nx,ny) and g[nx][ny] == blank: # ! 비버 이동 가능
                if t + 1 < water_time[nx][ny]: # ! 물이 차는 시간보다 작은 경우에만 이동 가능
                    if t + 1 < dis[nx][ny]: # ! 기존 최단시간보다 작은 경우에 갱신
                        dis[nx][ny] = t + 1
                        dq.append((nx,ny,t+1))
            elif isInner(nx,ny) and g[nx][ny] == des: # ! 도착점
                if t + 1 < water_time[nx][ny]:
                    if t+1 < dis[nx][ny]:
                        dis[nx][ny] = t + 1 # ! 도착점은 시간만 갱신
BFS(startX, startY)
if dis[endX][endY] == INF:
    print("KAKTUS")
else:
    print(dis[endX][endY])

*** 다익에서 중요한 건 시작점이 고정되어 있는 경우에 값을 최단거리(시간)로 갱신해 나갈 때 위와 같이 값을 갱신해 나가면 된다.
또한 도착점에 도달했을 경우에는 값이 갱신되는지만 확인하고, 큐에 따로 넣지 않는다.

• 끝나야 하니깐 !

기본적으로 다익스트라는 시작 지점이 정해져 있을때 갱신 가능할때 큐에 넣어서 하는거고

플로이드는 시작 지점이 정해지지 않았을때 모든 정점들을 거쳐서 모든 정점에 도달할 수 있는 최단 거리를 구하는 거고

또한 트랩, 함정을 미리 파악해두고 갱신해 나갈 수도 있다는 것을 기억하자.

해당 문제와 함께 백준 2636 치즈 문제도 꼭 풀어보자.