[Baekjoon] 2176번 : 합리적인 이동경로

1. 문제

https://www.acmicpc.net/problem/2176

• DP 문제

// 문제
그래프의 한 정점 S에서 다른 한 정점 T로 이동하려 한다. 
이동할 때 T에 가까워지며 이동하는 경우, 이를 합리적인 이동경로라 한다. 
물론 이러한 경로는 최단경로가 아닐 수도 있다.

그래프가 주어졌을 때 
가능한 합리적인 이동경로의 개수를 구하는 프로그램을 작성하시오. 
S = 1, T = 2 인 경우로 한다.

// 입력
첫째 줄에 정점의 개수 N(1 < N ≤ 1,000), 
간선의 개수 M(1 ≤ M ≤ 100,000이 주어진다. 
다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 
이는 A번 정점과 B번 정점이 길이 C(0 < C ≤ 10,000)인 
간선으로 연결되어 있다는 의미이다. 
두 정점은 최대 한 개의 간선으로만 연결될 수 있다. 간선은 방향성이 없다.

// 출력
첫째 줄에 답을 출력한다. 
답은 2147483647을 넘지 않는다.

// 예제 입력 1 
4 4
1 3 1
3 2 2
1 4 2
2 4 1

// 예제 출력 1 
2

2. 핵심 아이디어

3. Python 문제풀이

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

n, m = map(int, input().split())
s, t = 1, 2
graph = [[] for _ in range(n+1)]
dist = [INF for _ in range(n+1)]
dp = [0 for _ in range(n+1)]

for _ in range(m) :
  a, b, c = map(int, input().split())
  graph[a].append([b, c])
  graph[b].append([a, c])

heap = [[0, t]]
dist[t] = 0
dp[t] = 1

while heap :
  cur_dist, now = heapq.heappop(heap)
  if cur_dist > dist[now] :
    continue
  for next, next_dist in graph[now] :
    total = next_dist + cur_dist
    if total < dist[next] :
      dist[next] = total
      heapq.heappush(heap, [total, next])
    if cur_dist > dist[next] :
      dp[now] += dp[next]

print(dp[s])

4. Java 문제풀이