무방향 가중치 연결 그래프가 하나 있다고 가정해 보겠습니다. 이 그래프는 n개의 노드로 구성되어 있으며, 각 노드에는 1부터 n까지의 레이블이 붙어 있습니다.
여기서 경로(path)는 [z0, z1, z2, ..., zk]처럼 노드를 나열한 것으로, z0은 시작 노드, zk는 끝 노드를 의미하며, 모든 i(0 ≤ i ≤ k-1)에 대해 zi와 zi+1 사이에 간선이 존재해야 합니다. 경로의 거리(distance)는 해당 경로에 포함된 간선들의 가중치 합입니다.
또한 dist(x)는 노드 n에서 노드 x까지의 최단 거리를 나타냅니다. 이때 제한된 경로(restricted path)란 모든 i(0 ≤ i ≤ k-1)에 대해 dist(zi) > dist(zi+1) 조건을 만족하는 특수한 경로를 말합니다. 즉, 끝 노드 쪽으로 갈수록 최단 거리가 항상 작아지는 경로만 허용됩니다.
따라서 우리가 구해야 할 것은 노드 1에서 노드 n까지의 제한된 경로의 개수입니다. 만약 답이 너무 커진다면 10^9 + 7로 나눈 나머지를 반환하면 됩니다.
예제 입력과 출력
예를 들어 아래와 같은 그래프가 주어졌다고 가정해 보겠습니다.
이 경우 출력 결과는 3입니다. 제한된 경로는 총 세 가지로, (1, 2, 5), (1, 2, 3, 5), (1, 3, 5)입니다.
해결 접근 방식
이 문제는 다익스트라(Dijkstra) 알고리즘과 동적 계획법(DP)을 결합하여 해결할 수 있습니다. 다익스트라 알고리즘으로 각 노드에서 노드 n까지의 최단 거리를 먼저 계산하고, 그 과정에서 최단 거리가 더 작은 인접 노드의 경로 수를 누적해 나가는 방식입니다. 구체적인 단계는 다음과 같습니다.
주어진 간선 리스트로 그래프의 인접 리스트(graph)를 생성합니다.
크기가 (n+1)인 배열 paths를 만들고 0으로 초기화한 뒤, paths[n] := 1로 설정합니다.
크기가 (n+1)인 배열 dists를 만들고 -1로 초기화합니다. 이 배열은 각 노드의 최단 거리를 저장합니다.
우선순위 큐 q를 생성하고, 초기값으로 (0, n)을 삽입합니다.
q가 비어 있지 않은 동안 다음을 반복합니다.
(dist, node) := q에서 가장 작은 원소를 꺼냅니다.
dists[node]가 이미 -1이 아니라면(방문 처리된 경우) 다음 반복으로 넘어갑니다.
dists[node] := dist로 설정합니다.
graph[node]의 각 인접 노드 v와 가중치 w에 대해:
dists[v]가 -1이라면 아직 방문하지 않은 것이므로 (dist + w, v)를 q에 삽입합니다.
그렇지 않고 dists[v] < dists[node]라면, v가 목적지에 더 가까운 노드이므로 paths[node] += paths[v]로 경로 수를 누적합니다.
node가 1이라면 paths[node] mod (10^9 + 7)을 반환합니다.
반복이 끝날 때까지 도달하지 못했다면 0을 반환합니다.
Python 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
from heapq import heappop, heappush
def solve(n, edges):
graph = defaultdict(dict)
for u, v, w in edges:
graph[u][v] = w
graph[v][u] = w
paths = [0] * (n+1)
paths[n] = 1
dists = [-1] * (n+1)
q = [(0, n)]
while q:
dist, node = heappop(q)
if dists[node] != -1:
continue
dists[node] = dist
for v, w in graph[node].items():
if dists[v] == -1:
heappush(q, (dist + w, v))
elif dists[v] < dists[node]:
paths[node] += paths[v]
if node == 1:
return paths[node] % (10**9 + 7)
return 0
n = 5
edges = [(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]
print(solve(n, edges))입력
5,[(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]
출력
3
코드 설명
이 코드는 우선순위 큐(heapq)를 활용해 노드 n에서 출발하는 다익스트라 탐색을 수행합니다. 노드를 꺼낼 때마다 해당 노드의 최단 거리를 확정하고, 인접 노드 중 이미 최단 거리가 확정된 노드이면서 현재 노드보다 목적지에 더 가까운(dist 값이 작은) 노드의 경로 수를 현재 노드에 더해 줍니다. 이렇게 하면 노드 1에 도달했을 때 paths[1]에 제한된 경로의 총 개수가 누적됩니다. 시간 복잡도는 O(E log V)로, 간선 수 E와 노드 수 V에 비례하여 효율적으로 동작합니다.