[BOJ] 1948 - 임계경로 (Python)

 

 

아이디어

 

위상 정렬로 각 도시에 도착하는 가장 늦는 시간을 구한 뒤, 도착지로부터 역으로 쉬지 않고 달리는 도로를 찾아 나간다.

 

 

풀이

 

입력 값들의 관계에 따라 출발 도시 리스트 parent와 도착 도시 리스트 child에 도시와 시간을 저장하고,

입력차수 리스트 degree에서 도착 도시 번호의 입력차수 값을 증가시켜 나간 후 함수 find_time과 find_road를 호출한다.

 

함수 find_time는 BFS로 각 도시에 도착하는 가장 늦는 시간을 구해 리스트 max_time에 저장한다.

가장 늦는 시간을 구하기 위해 방문하려는 도시의 진입차수 degree 값이 0이 되면 큐에 넣고 탐색하도록 한다.

 

함수 find_road는 BFS로 두 도시의 max_time 값의 차를 구해 해당 도로를 지나는 시간과 같다면 결과값을 증가시킨다.

이때 방문은 한 번만 이뤄지면 되므로 방문 표시 리스트 visited로 방문 여부를 확인하고 큐에 넣어 탐색한다.

도착지로부터 BFS를 해야 임계 경로가 아닌 도로들을 제외해 나가며 해당 도로의 임계 경로 여부를 파악할 수 있다.

 

import sys

input = sys.stdin.readline

def find_time():
    queue = [start]
    while queue:
        idx = queue.pop(0)
        for i, t in child[idx]:
            max_time[i] = max(max_time[i], max_time[idx]+t)
            degree[i] -= 1
            if degree[i] == 0:
                queue.append(i)

def find_road():
    queue = [end]
    visited = [0]*(n+1)
    res = 0
    while queue:
        idx = queue.pop(0)
        for i, t in parent[idx]:
            if max_time[idx]-max_time[i] == t:
                res += 1
                if not visited[i]:
                    queue.append(i)
                    visited[i] = 1
    return res

n = int(input())
m = int(input())
child = [[] for _ in range(n+1)]
parent = [[] for _ in range(n+1)]
degree = [0]*(n+1)
for _ in range(m):
    s, e, t = map(int, input().split())
    child[s].append((e, t))
    parent[e].append((s, t))
    degree[e] += 1
start, end = map(int, input().split())
max_time = [0]*(n+1)
find_time()
print(max_time[end])
print(find_road())

 

 

가장 늦는 시간을 구할 때 위상 정렬을 하지 않으면 불필요한 재탐색이 반복되어 시간 초과가 발생한다.

도착 도시 방문 이전에 해당 도시로 가는 모든 출발 도시에 대한 방문이 이뤄져야 하므로 위상 정렬이 사용된다.

# 시간 초과 코드
queue = [start]
while queue:
    idx = queue.pop(0)
    for i, t in child[idx]:
        max_time[i] = max(max_time[i], max_time[idx]+t)
        queue.append(i)