백준 1948번: 임계경로

백준 1948번: 임계경로

풀이 과정

바로 이전에 백준 5719번: 거의 최단 경로를 풀어서 역추적 BFS 아이디어가 쉽게 떠올랐다.

정답 코드

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


N, M = int(input()), int(input())
L, L_reverse = defaultdict(list), defaultdict(list)
C = [0] * (N + 1)
for i in range(M):
    a, b, c = map(int, input().split())
    L[a].append((b, c))
    L_reverse[b].append((a, c))
    C[b] += 1
start, end = map(int, input().split())
    
Q = deque()
Q.append((0, start))

D = [0] * (N + 1)
while Q:
    SD, SN = Q.popleft()

    for FN, FD in L[SN]:
        C[FN] -= 1
        D[FN] = max(D[FN], SD + FD)
        if not C[FN]:
            Q.append((D[FN], FN))

Q = deque()
Q.append(end)

V = defaultdict(int)
V[end] = 1

count = 0
while Q:
    SN = Q.popleft()

    for FN, FD in L_reverse[SN]:
        if FD + D[FN] == D[SN]:
            count += 1
            if not V[FN]:
                Q.append(FN)
                V[FN] = 1

print(D[end])
print(count)

반성할 점

역추적 BFS 과정에서 정점 방문 여부를 기록하는 이유는 이후의 중복 카운팅을 막기 위해서이다. 그렇다고 방문한 정점으로의 간선을 카운팅하지 않으면 안 된다. 덕분에 30분 시간 낭비했다.