[백준/2176] 합리적인 이동경로 (Python)

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

2176번: 합리적인 이동경로

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:27:09

 

---

 

문제 설명

 

 

그래프의 한 정점 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을 넘지 않는다.

 

입력 예시

 

4 4
1 3 1
3 2 2
1 4 2
2 4 1

 

출력 예시

 

2

 

 

---

 

풀이

 

이동할 때 T에 가까워지는지의 여부를 체크해보려면, 각 정점에서 T와의 거리를 알 수 있어야 한다. 간선 및 정점의 개수를 고려할 때 O(ElogV)의 시간복잡도를 갖는 다익스트라 알고리즘을 사용해보자.

 

이렇게 정점에서 T까지의 거리를 모두 알 수 있다면, 다음은 합리적인 이동경로를 탐색해야 한다. 이 역시 완전탐색으로는 비효율적인 시간 소모를 야기하게 된다. 따라서 DP를 한 움큼 가미해보자. 이미 방문한 정점에서의 합리적인 이동경로 갯수가 있다면, 이 이동경로 갯수를 불러와 사용할 수 있다.

 

풀이 코드

from collections import defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
MAX = float('inf')
N, M = map(int, input().split())
edge_list = defaultdict(list)
for _ in range(M) :
  a, b, dist = map(int, input().split())
  edge_list[a-1].append((b-1, dist))
  edge_list[b-1].append((a-1, dist))

dp = [-1]*N
dist_list = [MAX]*N
dist_list[1] = 0
q = [ (0, 1) ]

def dfs(node) :
  if node == 1 :
    return 1
  if dp[node] > -1 :
    return dp[node]

  result = 0
  for nxt, _ in edge_list[node] :
    if dist_list[node] > dist_list[nxt] :
      result += dfs(nxt)
  dp[node] = result
  return dp[node]

while q :
  dist, node = heappop(q)

  if dist_list[node] < dist :
    continue

  for nxt, nxt_dist in edge_list[node] :
    if dist_list[nxt] > dist + nxt_dist :
      dist_list[nxt] = dist + nxt_dist
      heappush(q, (dist + nxt_dist, nxt))

if dist_list[0] == MAX :
  print(0)
else :
  print(dfs(0))

풀이 완료!