[백준 2008번] 사다리 게임 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,M = map(int,input().split())    #가로 n 세로 m
a,b,erase,draw = map(int,input().split())

graph = {(n,m):[((n,m+1),0)] for n in range(1,N+1) for m in range(M+1)}
for m in range(M):
  n = int(input())
  graph[(n,m)] = [((n+1,m+1),0),((n,m+1),erase)]
  graph[(n+1,m)] = [((n,m+1),0),((n+1,m+1),erase)]

for n in range(1,N+1):
  for m in range(M+1):
    if n != N:
      graph[(n,m)].append(((n+1,m),draw))
    if n != 1:
      graph[(n,m)].append(((n-1,m),draw))

DP = {(n,m):1e9 for n in range(1,N+1) for m in range(M+1)}
hq = []
heappush(hq,(0,(a,0)))
while hq:
  w,now = heappop(hq)
  if DP.get(now,-1)==-1 or DP[now] <= w:
    continue
  DP[now] = w
  if graph.get(now):
    for next,w1 in graph[now]:
      heappush(hq,(w+w1,next))

print(DP[(b,M)])

어려운 문제였다.

아이디어도 떠올리기 쉽지 않았는데 구현도 까다로웠던 문제. 다 익스트라로 해결하였다.

 

알고리즘을 요약하면,

1. 사다리의 각 좌표를 노드로 생각한다. (몇번째 세로선의 몇번째 가로선인지 (n,m)으로)

2. 일단 모든 좌표에 대해서 아래로 내려가는 가중치 0의 간선이 존재한다고 놓는다.

3. M개의 숫자가 입력되면, 해당 노드는 아래로 내려가는 간선의 가중치를 0이 아닌 지우는데 드는 비용(erase)으로 바꾸고, 옆으로 이동하는 가중치 0의 간선을 추가한다.

4. 모든 노드에 대해서 옆으로 이동하는 간선을 만들고, 이때의 가중치는 그리는데 드는 비용(draw)이다.

5. (a,0) 노드에서 (b,M) 노드까지의 최단거리를 다 익스트라 알고리즘으로 구한다.

 

 

다 익스트라로 풀 수 있다는 사실을 숨겨놓아서 떠올리기 쉽지 않았는데, 떠올렸을때는 "이런 문제도 다 익스트라로 풀 수 있다니" 하는 쾌감도 있었다.

재미있는 문제였다.

 

오늘의 교훈) 문제의 본질을 파악하여 어떤 알고리즘을 이용해야할지 판단하자