[파이썬/python] 백준 - 1948 임계경로

문제

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

---

문제 설명

1. 모든 도로가 일방통행이고, 사이클이 없는 나라가 있다.
2. 이 나라의 지도를 그리기 위해 무수히 많은 사람들이 시작 도시에서 출발하여 도착 도시까지 가능한 모든 경로를 탐색한다.
3. 모든 사람들이 각자의 일을 마치고 도착 도시에서 만났을 때, 최소 몇시간 후에 만날 수 있을까?
   1. 모두가 만나기 위해서는 마지막 사람까지 도시에 도착해야 한다.
   2. 어떤 사람은 이 시간에 만나기 위해, 1분도 쉬지 않고 달려야 한다.
   3. 출발 도시로 들어오는 도로와, 도착 도시에서 나가는 도로는 0개이다.
4. 이 때 도로의 수를 구한다.

 

---

풀이

처음 문제를 보고 무엇을 구하라고 하는 것인지 이해하기 힘들었다.

모든 사람들이 일을 마치고 도착 도시에서 만나야 한다. 즉 가장 늦은 사람까지 도착 도시에 도착을 해야하기 때문에, 결국 가장 오래걸린 시간일 때, 지나온 도로를 모두 구하라는 말이다.

문제 자체가 이해가 안돼서 문제를 이해하는데 더 오랜 시간을 쏟았던 것 같다.

 

처음에는 다익스트라를 떠올렸다. 하지만 다익스트라 알고리즘은 최단거리를 구하는 알고리즘이기에, 최장거리를 구할 수는 없었다. 그래서 위상정렬을 통해 시작 도시부터 순차적으로 탐색하면서 최장 거리를 갱신했다.

하지만, 문제는 어떻게 최장 거리일 때 지난 도로들을 탐색하느냐였다. 지나온 길을 모두 알아야 하기 때문에, 역순으로 돌아가서 탐색을 해야한다고 생각했다.

 

최초엔 진입차수가 0인 노드를 탐색할 시점에 해당 노드로 이동이 가능했던 이전 노드들의 거리를 비고해서, 해당 간선들을 배열에 넣고 결과를 출력했다. 하지만 매번 이전 모든 노드들을 탐색하니, 처음에는 메모리 초과가 발생했고, 이를 set으로 해결하니, 다음은 시간초과가 발생했다. 너무 중복된 간선이 많아 시간이 오래걸리는 것 같았다.

 

시간초과를 해결하기 위해 거리를 모두 갱신한 후에 역추적을 해보기로 했다.

도착 도시에서 들어올 수 있는 진입 노드들의 가중치를 빼가며, 현재 최장 거리와 일치하는지 판단했다. 일치한다면, 해당 도로는 지나왔던 간선이므로 결과에 더해줬다.

 

이 문제의 핵심은 위상정렬 후 역추적을 통해 지나온 간선을 탐색하는 것이라 생각한다. 

 

1. 기본 그래프와, 역추적을 위한 리버스 그래프를 초기화한다.
2. 위상 정렬을 통해, 모든 노드의 최장거리를 탐색한다.
3. 도착지점부터 BFS를 진행하여 최장거리 비교를 통해, 역추적하여 지나온 간선들을 탐색한다.
4. 도로의 총 개수를 출력한다.

---

코드

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
reverse_graph = [[] for _ in range(n+1)]
indegree = [0 for _ in range(n+1)]
dist = [-1 for _ in range(n+1)]

for _ in range(m):
    v1, v2, cost = map(int, input().split())
    graph[v1].append((v2, cost))
    reverse_graph[v2].append((v1, cost))
    indegree[v2] += 1

s, e = map(int, input().split())
dist[s] = 0
queue = deque([s])

while queue:
    v1 = queue.popleft()
    for v2, cost in graph[v1]:
        if dist[v2] < dist[v1] + cost:
            dist[v2] = dist[v1] + cost
        indegree[v2] -= 1
        if indegree[v2] == 0:
            queue.append(v2)

res = 0
visited = [0 for _ in range(n+1)]
queue = deque([e])
visited[e] = True

while queue:
    v1 = queue.popleft()
    for v2, cost in reverse_graph[v1]:
        if dist[v1] == dist[v2] + cost:
            res += 1
            if visited[v2]:
                continue
            visited[v2] = 1
            queue.append(v2)

print(dist[e])
print(res)

---

시간복잡도

• 위상정렬의 시간복잡도는 BFS와 유사한 방식으로 작동하기 때문에 O(V + E)이다. 또한 역추적 시에도 O(V+E)이다.
• 즉 총 시간복잡도는 약 $O(2*(V+E))$이다.
• 최악의 경우 $V = 10^4, E = 10^5$이므로 약$O(10^5)$의 시간복잡도가 소요된다.