1. 문제 설명

임계경로

2. 문제 분석

위상 정렬에 DP를 적용해 해당 노드에 대한 최장 거리를 구할 수 있다. 이를 응용해 최장 거리에 사용되는 간선을 BFS를 통해 거꾸로 역추적하자.

• 거의 최단 경로라는 문제에서 비슷한 기법으로 풀었는데, 그때에는 다익스트라를 통해 최단 거리를 구한 뒤, 거꾸로 BFS를 통해 최장 경로에 사용된 경로를 비활성화했다. 특히 기존 그래프를 거꾸로 만든 뒤 도착지에서 출발지로 역추적하면서 distances 또는 dp에 기록된 바와 맞다면 최단/최장 경로임이 보장된다는 점에서 보다 메모리/시간 효율적으로 문제를 풀 수 있다.

3. 나의 풀이

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
nodes = [[] for _ in range(n+1)]
nodes_inv = [[] for _ in range(n+1)]
in_degree = [0 for _ in range(n+1)]

for _ in range(m):
    tail, head, cost = map(int, sys.stdin.readline().rstrip().split())
    nodes[tail].append([head, cost])
    in_degree[head] += 1
    nodes_inv[head].append([tail, cost])

start, end = map(int, sys.stdin.readline().rstrip().split())

def topological_sort():
    queue = deque()
    dp = [0 for i in range(n+1)]
    for i in range(1, n+1):
        if in_degree[i] == 0:
            queue.append([i, 0])

    while queue:
        cur_node, cur_cost = queue.popleft()

        for next_node, next_cost in nodes[cur_node]:
            in_degree[next_node] -= 1
            dp[next_node] = max(dp[next_node], next_cost + dp[cur_node])
            if in_degree[next_node] == 0:
                queue.append([next_node, cur_cost + next_cost])

    return dp
# 위상 정렬을 dp를 통해 값을 누적시키면서 정렬. 각 도시별로 가는 최장 거리를 기록한다.

dp = topological_sort()

edges = set()
def BFS():
    queue = deque()
    queue.append([end, 0])
    # nodes_inv는 그래프의 head와 tail을 거꾸로 만든 그래프

    while queue:
        cur_node, cur_cost = queue.popleft()

        for post_node, post_cost in nodes_inv[cur_node]:
            if dp[cur_node] == post_cost + dp[post_node] and tuple((post_node, cur_node)) not in edges:
                # post_cost를 사용한 루트가 최장 거리일 때에만 추적한다. 이때 중복 간선을 체크하기 위해 set으로 확인.
                edges.add(tuple((post_node, cur_node)))
                queue.append([post_node, cur_cost+post_cost])
BFS()

print(dp[end])
# end까지 간선으로 이동하는 최장 거리
print(len(edges))
# 최장거리 루트에 사용된 간선의 개수