[Python][백준 2176][다익스트라,DP] 합리적인 이동경로 - 컴도리돌이

반응형

2176번: 합리적인 이동경로

---

풀이 과정

 

DP를 최단 경로를 탐색하기 위하여 사용된다. dp의 i번째 인덱스는 출발하는 합리적인 이동경로의 수를 의미하며, 도착점 2번 노드부터 탐색을 시작한다. 각 정점까지의 최단경로를 갱신하는 과정에서 현재 노드까지 최단 경로의 길이가 다음 노드까지 최단 경로의 길이보다 짧을 경우, 다음 노드와 현재 노드 사이에 합리적인 이동 경로가 존재한다는 뜻이다.

---

풀이 과정

import sys,heapq; input = sys.stdin.readline ; INF = 2147483647

#  정점의 개수, 간선의 개수 
n,m = map(int,input().split())
s,t = 1,2

# 간선 연결 정보(graph), 이동 거리(dist), 최단 경로(dp)
graph,dist,dp = [[] for _ in range(n+1)],[INF for _ in range(n+1)],[0 for _ in range(n+1)]

# a번과 b번의 연결 길이 c, m번 입력 받음
for _ in range(m) : 
  a,b,c = map(int,input().split())
  graph[a].append([b,c])
  graph[b].append([a,c])

# min-heap, 거리[t] = 0, 최단경로[t] = 1 초기화
heap,dist[t],dp[t] = [[0,t]],0,1
while heap :
  # 현재까지 이동 거리, 현재 정점
  curDist,cur = heapq.heappop(heap)
  # 현재거리가 저장된 이동거리보다 긴 경우 continue
  if curDist > dist[cur] : continue
  
  # 다음 정점, 현재 거리와 연결된 길이
  for next,nextDist in graph[cur] :
    # 다음 정점까지 총 거리 = 다음 정점까지 연결된 길이 + 현재 이동 거리
    Dist_ = nextDist + curDist  
    # 다음 정점까지 총 거리가 저장된 거리보다 짧을 경우 heap에 저장
    if Dist_ < dist[next] :
      dist[next] = Dist_
      heapq.heappush(heap,[Dist_,next])
    # 다음 정점까지 이동거리가 현재 이동 거리보다 짧을 경우 합리적인 이동 경로
    if curDist > dist[next] :
      dp[cur] += dp[next]
print(dp[s])