[백준] 임계경로

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

1948번: 임계경로

골드 2를 찍기 위해 친구가 추천해준 문제를 풀어보았습니다. 위상정렬을 사용하여 해결한 문제입니다. 일방향 통행, 싸이클이 없다는 두개의 조건을 보고 위상정렬이 떠올랐습니다. 위상정렬을 하면서 현재 노드까지의 최대거리를 갱신해줍니다. 그리고 최대거리로 갱신해준 노드들을 저장해둡니다. 그 다음으로는 도착점을 시작으로 현재 노드들을 최대거리로 갱신해준 노드들을 역으로 탐색해나가면 정답을 얻을 수 있습니다. 

 

import sys
from collections import defaultdict, deque

graph = defaultdict(list)

sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n = int(input())
m = int(input())

in_node = [0] * (n + 1)
# 각 노드의 최대 거리를 계산하여 가지고 있음
dist = [0] * (n + 1)

# 최대값으로 업데이트한 마지막 노드들을 가지고 있는다.
last_update = [[]] * (n + 1)

for _ in range(m):
    fr, to, weight = tuple(map(int, input().split()))
    in_node[to] += 1
    graph[fr].append((to, weight))

start, end = tuple(map(int, input().split()))

q = deque([start])

while q:
    cur = q.popleft()

    for next_node, weight in graph[cur]:
        in_node[next_node] -= 1

        cur_dist = dist[cur] + weight

        # 최대 거리를 갱신하면 현재 노드를 넣어준다.
        if dist[next_node] < cur_dist:
            dist[next_node] = cur_dist
            last_update[next_node] = [cur]
        # 같은 최대 거리라면 추가해준다.
        elif dist[next_node] == cur_dist:
            last_update[next_node].append(cur)

        # 큐에 추가
        if in_node[next_node] == 0:
            q.append(next_node)

q = deque([end])
ans = 0
visited = [False] * (n + 1)
visited[end] = True
ans += len(last_update[end])
# 끝지점을 시작으로 현재 자신을 최대 경로로 갱신해줬던 노드들을 탐색한다.
while q:
    cur = q.popleft()

    for next_node in last_update[cur]:
        # 아직 방문되지 않은 노드라면 해당 노드를 최대 거리로 갱신했던 노드들의 개수를 더해준다.
        if not visited[next_node]:
            visited[next_node] = True
            ans += len(last_update[next_node])
            q.append(next_node)

print(dist[end])
print(ans)