[백준 1948번] 파이썬 - 임계경로

백준 1948 - 임계경로

시간 제한 2초, 메모리 제한 512MB

# 조건

• 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다.
• 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.
• 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다.
• 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가?
  • 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.
• 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다.
• 이런 사람들이 지나는 도로의 수를 카운트 하여라.
• 출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

입력

• 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다.
• 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다.
• 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다.
• 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다.
• 그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.
• 모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.

출력

• 첫째 줄에는 이들이 만나는 시간을, 둘째 줄에는 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 출력하여라.

# 접근 방법

• 최단 경로가 아닌 최대 경로를 찾는 문제이다.
• 또한, 최대 경로가 여러 개인 경우 지나온 도로의 개수를 중복되지 않게 카운트 해주어야 한다.
• bfs를 이용하여 모든 경로와 가중치를 기록해주면서 목적지에 도착하였을 떄 갱신해준다면 시간 초과, 메모리 초과를 받게 된다.
• 따라서 위상 정렬을 이용하여 목적지까지의 최대 비용을 구해주고, 역추적을 통하여 최대 비용에 해당하는 도로들의 개수를 구해준다.
  • 현재 이동하려는 곳에 기록된 값이 현재 비용보다 작다면 갱신해주고 만약 차수가 0이 되었다면, 모든 경로를 체크한 것이므로 q에 넣어준다.
  • 목적지를 q에 넣어주고 역으로 추적하는데, 현재 기록된 비용 - 이동할 곳에 기록된 비용 == 이동할 노드의 가중치치 값과 같다면 cnt += 1을 해준다.
  • 또한 중복 방문을 하지 않도록 check 리스트에 표시해준 후 q에 담아준다.

    시간 초과 및 메모리 초과 코드

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

def bfs():  
    global dist, route  
    q = deque()  
    q.append((st, 0, []))  
    while q:  
        now, val, r = q.popleft()  
        if now == en:  
            if val > dist:  
                route.clear()  
                dist = val  
                for j in r:  
                    route.add(j)  
            elif val == dist:  
                for j in r:  
                    route.add(j)  
            else:  
                continue  
        for next_node, next_val in info[now]:  
            if visited[next_node] or next_node == en:  
                q.append((next_node, val+next_val, r + [(now, next_node)]))  
                visited[next_node] -= 1  

N = int(input())  
M = int(input())  
info = [[] for _ in range(N+1)]  
visited = [0] * (N+1)  
for _ in range(M):  
    a, b, c = map(int, input().split())  
    info[a].append((b, c))  
st, en = map(int, input().split())  
nq = deque()  
nq.append(st)  
visited[st] = 1  
while nq:  
    now = nq.popleft()  
    for ne, _ in info[now]:  
        visited[ne] += 1  
        nq.append(ne)  
dist = 0  
route = set()  
bfs()  

print(dist)  
print(len(route))

pass 코드

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

def topology_sort():  
    q = deque()  
    q.append(st)  
    while q:  
        cur = q.popleft()  
        for n_node, w in info[cur]:  
            degree[n_node] -= 1  
            v = dist[cur] + w  
            if dist[n_node] < v:  
                dist[n_node] = v  
            if degree[n_node] == 0:  
                q.append(n_node)  
    return dist[en]  

def back():  
    cnt = 0  
    q = deque()  
    q.append(en)  
    check = [False] * (N+1)  
    while q:  
        cur = q.popleft()  
        for n_node, w in b_info[cur]:  
            if dist[cur] - dist[n_node] == w:  
                cnt += 1  
                if not check[n_node]:  
                    check[n_node] = True  
                    q.append(n_node)  
    return cnt  


N = int(input())  
M = int(input())  
info = [[] for _ in range(N+1)]  
b_info = [[] for _ in range(N+1)]  
degree = [0] * (N+1)  
for _ in range(M):  
    a, b, c = map(int, input().split())  
    info[a].append((b, c))  
    b_info[b].append((a, c))  
    degree[b] += 1  
st, en = map(int, input().split())  
dist = [0] * (N+1)  
print(topology_sort())  
print(back())