[백준 파이썬 1948번 임계경로] 위상정렬 응용과 역추적의 활용

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

1948번: 임계경로

이번 문제도 위상정렬을 활용하면 최장경로를 구하는 것에는 어려움이 없다.

 

이번 문제 핵심은

중복되지 않게 도로의 개수를 구해라

 

중복을 제거하기 위해서 역추적을 통해서 set에 간선을 저장한다

역추적을 하기 위해 노드를 이동할 때 이전 노드를 기억시킬 배열이 필요하고

이는 노드의 최대값이 갱신되거나 같을 때 이전 노드를 기억시킨다.

---

위상정렬 두 문제를 풀어 보았는데

위상정렬은 다른 알고리즘과 곁들여 쓰기 좋은 알고리즘인 듯 하다.

위상정렬 + 역추적(다익스트라), 위상정렬 + 최대힙 과 같이

위상정렬로 탐색 순서를 설정할 수 있다는 것이 가장 큰 장점인 것 같다.

---

코드 첨부

import sys
from collections import deque
input = sys.stdin.readline


def topo():
    q = deque([start])
    while q:
        now = q.popleft()
        for nxt, ndist in graph[now]:
            if dist_ls[nxt] < dist_ls[now] + ndist:
                dist_ls[nxt] = dist_ls[now] + ndist
                back_ls[nxt] = [now]
            elif dist_ls[nxt] == dist_ls[now] + ndist:
                if now not in back_ls[nxt]:
                    back_ls[nxt].append(now)
            topo_ls[nxt] -= 1
            if topo_ls[nxt] == 0:
                q.append(nxt)


def backpropagation():
    ans_ls = set()
    back_q = deque([end])
    while back_q:
        now = back_q.popleft()
        for nxt in back_ls[now]:
            ans_ls.add((now, nxt))
            if nxt not in back_q:
                back_q.append(nxt)

    print(dist_ls[end])
    print(len(ans_ls))


N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
topo_ls = [0 for _ in range(N+1)]
dist_ls = [0 for _ in range(N+1)]
back_ls = [[] for _ in range(N+1)]
for _ in range(M):
    u, v, d = map(int, input().split())
    graph[u].append([v, d])
    topo_ls[v] += 1

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

topo()
backpropagation()