[백준 2176번] 합리적인 이동경로 (Python3)

import sys
input = sys.stdin.readline
from heapq import *

def Dijkstra():
  DP = [1e9]*N
  hq = [(0,1)]
  while hq:
    w,now = heappop(hq)
    if DP[now] <= w:
      continue
    DP[now] = w
    for next,w1 in graph[now]:
      heappush(hq,(w+w1,next))
  return DP

def DFS(now):
  for next,w in graph[now]:
    if Dij[now] <= Dij[next]:
      continue
    if not DP[next]:
      DFS(next)
    DP[now] += DP[next]

N,M = map(int,input().split())

graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = map(int,input().split())
  graph[a-1].append((b-1,c))
  graph[b-1].append((a-1,c))

Dij = Dijkstra()
DP = [0]*N; DP[1] = 1
DFS(0)
print(DP[0])

간단한 다 익스트라 + DFS + DP 문제

알고리즘은 여러개 쓰이지만 풀이는 매우 간단하다.

 

설명하면,

1. 다 익스트라로 2번 노드에서 모든 노드까지의 최단거리를 측정한다.

2. DFS + DP로 최단거리가 작아지는 경우에만 탐색을 하며 경우의 수를 센다.

 

골드 1 문제 정도는 이제 대부분 가볍게 풀 수 있는 수준이 된 것 같다. 앞으로도 열심히 해야겠다.

 

 

오늘의 교훈) 플래티넘도 가볍게 풀 수 있을 때까지 화이팅