[파이썬/python] 백준 - 2176 합리적인 이동경로

문제

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

---

문제 설명

1. 그래프의 한 정점 S에서 다른 한 정점 T로 이동하려 한다.
2. 이동할 때 T로 가까워지며 이동하는 경우, 이를 합리적인 이동경로라고 한다.
   1. 합리적인 이동 경로는 최단경로가 아닐 수 있다.
3. 그래프가 주어질 때 합리적인 이동경로의 개수를 구하라.
   1. 이 때 S = 1, T = 2이다.

 

---

풀이

합리적인 이동경로라는 말이 정말 이해가 가지 않았다. 따라서 그림을 그려가며 이해했다.

 

예제

다음과 같은 그래프가 존재할 때 합리적인 이동경로를 생각해보자.

 

1에서 2로 갈 수 있는 경로는 총 2개이며, 최단거리는 3이다.

1 -> 3 -> 2 (dist = 3)

1 -> 4 -> 2 (dist = 5)

 

합리적인 이동경로란, 매 이동을 할 때마다 1에서 2까지의 거리가 가까워져야한다.

 

1번 경로부터 확인해보자.

1 -> 3으로 이동하면 남은 경로 3 -> 2의 거리는 2가 된다. 즉 1 -> 2의 최단 거리 3보다 1 감소된 거리다.

따라서 해당 경로는 합리적인 이동경로다.

 

다음은 2번 경로다.

1 -> 4로 이동하면 남은 경로 4 -> 2의 거리는 3이 된다. 1 -> 2의 최단 거리 3과 동일하다.

따라서 해당 경로는 합리적인 이동경로가 아니다.

 

하지만 이해가 가지 않는 부분이 1개 존재한다.

바로 문제에 적혀있던 조건 "합리적인 이동경로는 최단거리가 아닐 수 있다." 라는 말이다.

 

최단거리가 아닐 수 있다면, 1 -> 4 -> 2로 가는 경우도 결국에는 1->4로 이동하면, 2로 가는 거리가 5에서 3으로 줄어들었으니, 이 또한 합리적인 이동경로가 아닌가? 라고 생각할 수 있다는 것이다.

 

하지만 아니다. 합리적인 이동경로란. S에서 T로 가는 최단 거리를 기준으로 노드에서 노드로 이동할 때 최단거리보다 감소해야 한다는 말이다.

 

그렇다면, 최단거리가 아닌데, 합리적인 이동경로가 되는 경우는 무엇일까?

 

아래 예제를 확인해보자.

 

이 그래프에서 1에서 2로 갈 수 있는 경로는 2개이며, 최단 거리는 3이다.

1 -> 3 -> 2, dist = 3

1 -> 4 -> 2, dist = 9

 

마찬가지로 첫번째 경로부터 확인해보자.

1 -> 3으로 이동하면 남은 3 -> 2까지의 거리는 1이다. 즉 남은 거리가 3보다 감소했으므로 이는 합리적인 이동경로다.

 

두 번째 경로도 확인해보자.

단순히 본다면 1 -> 4 가 거리가 7이나 된다. 따라서 합리적인 이동경로가 불가능하다고 판단할 수 있다.

하지만 1 -> 4로 이동한다면 4 -> 2로가는 남은 거리는 2가된다. 최단 거리 3보다 감소했다.

따라서 이는 합리적인 이동경로가 되는 것이다.

 

이 내용을 정리해보자.

 

A -> B로 이동을 할 것이다.

그 때 B -> 2 까지의 거리가 A -> 2까지의 거리보다 감소한 상태여야 한다는 것이다.

 

즉 이 문제의 핵심은 2에서 각 노드들의 최단 거리를 전부 구하면 합리적인 이동경로가 맞는지 판단할 수 있다!

이쯤되면 최단거리를 구하는 하나의 알고리즘이 떠오른다.

 

특정 노드에서 다른 모든 노드들간의 최단 거리를 구하는 알고리즘인 다익스트라(dijkstra)를 사용해서 최단 거리를 구한 후

모든 경로를 탐색하며 합리적인 이동 경로의 개수를 누적해서 총 개수를 구하면 되는 것이다.

 

 

1. dijkstra를 통해 도착점인 2에서 다른 노드들의 최단 거리를 구한다.
2. 1부터 깊이 우선 탐색을 진행한다.
   1. 현재 경로가 합리적인 이동 경로라면, 재귀한다.
   2. 만약 현재 노드가 이미 탐색을 마친 노드라면 현재 개수를 return 한다.
3. 최종적으로 1번 노드에 모인 총 경로의 개수를 출력한다.

---

코드

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

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

graph = [[] for _ in range(N+1)]
for _ in range(M):
    v1,v2,c = map(int,input().split())
    graph[v1].append((v2,c))
    graph[v2].append((v1,c))

dist = [INF for _ in range(N+1)]

def dijkstra():
    dist[2] = 0
    hq = [(0,2)]
    heapq.heapify(hq)

    while hq:
        curr_cost, v1 = heapq.heappop(hq)
        if dist[v1] < curr_cost:
            continue
        for v2, cost in graph[v1]:
            if dist[v2] < cost + curr_cost:
                continue
            dist[v2] = cost + curr_cost
            heapq.heappush(hq,(dist[v2],v2))
dijkstra()

dp = [0 for _ in range(N+1)]
visited = [0 for _ in range(N+1)]

def dfs(v1):
    if dp[v1]:
        return dp[v1]
    
    for v2,cost in graph[v1]:
        if dist[v1] <= dist[v2]:
            continue
        dp[v1] += dfs(v2)


    return dp[v1]

dp[2] = 1
dfs(1)
print(dp[1])

---

시간복잡도

• 힙으로 구현한 dijkstra의 시간복잡도는 $O(ElogV)$이다.
• 또한 dfs의 시간복잡도는 $O(V + E)$이다.
  • *사실 프루닝을 통해 더 적은 시간이 걸리겠지만 시간복잡도이기 때문에 어림잡도록 하겠다.
• 즉 최대 계수인 $O(V + E) = O(10**5)$ 정도의 시간복잡도를 가질 것으로 예상된다.