[백준] 1948번 : 임계경로

1948번: 임계경로

1948번: 임계경로

🤔 문제분석

진입차수를 알고있으면 문제를 쉽게 접근 할 수 있습니다. 진입차수로 가장 오래걸리는 시간을 구한뒤, 진입 차수를 역추적하여 가장 큰 값이 방문된 곳들을 카운팅하여 문제를 해결 할 수 있습니다.

진입차수를 역추적 하는 방법은 간선의 정보를 거꾸로 입력받은뒤에 목적지로부터 소스까지 재 방문해봄으로서 문제를 해결 할 수 있습니다. 되돌아가는 과정에서 이미 구한 최대거리를 계산한 값을 확인해가면서 역추적 하면 됩니다.

예를들어 역추적 할때 5번 노드에서 3번노드 2번노드로 가야할경우, 5번, 3번, 2번 노드가 최대거리가 10, 5, 4 라고 한다면 5→ 3 간선의 길이가 5이어야하며, 5 → 2의 간선의길이는 6이어야한다. 그렇지 않은경우 최대거리가 아니기때문에 역추적의 후보에서 제외된다.

📝 의사코드

1. 진입차수 알고리즘을 활용하여 소스로부터 목적지까지의 최대거리를 계산한다.
2. 목적지로부터 소스까지 거꾸로 역추적하면서 간선의 개수를 구한다.

💻 코드

import sys
from collections import deque

input = sys.stdin.readline

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

in_degree = [0 for _ in range(n+1)]
distance = [0 for _ in range(n+1)]
edge = [[] for _ in range(n+1)]
r_edge = [[] for _ in range(n+1)]

for _ in range(m):
    start, end, cost = map(int, input().split())
    edge[start].append((end, cost))
    r_edge[end].append((start, cost))
    in_degree[end] += 1
    
start , end = map(int, input().split())
queue = deque()
queue.append((start, 0))

while queue:
    node, cost = queue.pop()
    
    for new_node, dst_cost in edge[node]:
        distance[new_node] = max(distance[new_node], cost + dst_cost)
        in_degree[new_node] -= 1
        if in_degree[new_node] == 0:
            queue.append((new_node, distance[new_node]))

queue = deque()
queue.append(end)
visited = [[False for _ in range(n+1)] for _ in range(n+1)]

cnt = 0
while queue:
    node = queue.pop()
    
    for new_node, new_cost in r_edge[node]:
        if distance[node] - new_cost == distance[new_node]:
            if not visited[node][new_node]:
                visited[node][new_node] = True
                cnt += 1
                queue.append(new_node)

print(distance[end])
print(cnt)

🎯 피드백 및 개선사항

처음에 문제를 접할때 진입차수로 문제를 접근하지 못하여 메모리 초과 판정을 받았습니다. 너비우선탐색으로 문제를 해결하였고, 큐에 너무 많은 값들이 적제 되었습니다. 진입차수를 활용한다면 예를들어 노드 3,4,5번이 6번 노드와 간선이 연결되어있다면, 기존에는 6번 노드를 3번 방문해야 했다면, 진입차수를 활용하면 1번만 방문할 수 있습니다.