[백준 2024/09/25] 1948번 임계경로

1. 문제

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

 

2. 접근 방법

최대 cost 를 0으로 채워두고, 해당 노드까지 방문할 cost 중 제일 높은 cost로 수정해주는 방식으로 적용하였다.

 

따라서 while dq 문을 수행하고 나면, cost 별 idx에 가장 높은 cost가 저장되어 있게 된다.

뒤에서 부터 앞으로 진행하며, (reverse_edges) 이용.

cost[u] == cost[v] + w 를 통해서 거리의 합이 최대가 될 수 있는 경로를 탐색하도록 구상한다.

 

해당 과정에서, stack 에 해당 노드를 넣었는지 유무를 파악하기 위해 visited 함수를 이용해 준다.

 

3. 코드

from collections import deque


def longest(start, end):
    cost = [0] * (n+1)
    reverse_edges = [[] for i in range(n+1)]

    dq = deque()
    dq.append(start)

    while dq:
        u = dq.popleft()

        for v, w in edges[u]:
            if cost[v] < cost[u] + w:
                cost[v] = cost[u] + w
            ind[v] -= 1
            reverse_edges[v].append([u, w])
            if ind[v] == 0:
                dq.append(v)

    stack = []
    visited = [False] * (n+1)
    stack.append(end)
    critical_cnt = 0
    while stack:
        u = stack.pop()

        for v, w in reverse_edges[u]:
            if cost[u] == cost[v] + w:
                critical_cnt += 1
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)

    print(cost[end])
    print(critical_cnt)


if __name__ == "__main__":
    n = int(input())
    m = int(input())
    edges = [[] for i in range(n+1)]
    ind = [0] * (n+1)

    for _ in range(m):
        u, v, w = map(int, input().split())
        edges[u].append([v, w])
        ind[v] += 1

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