[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1948번 _ 임계경로

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

1948번: 임계경로

[문제]

월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.

이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.

어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라.

출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

 

[입력]

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

그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.

모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.

[출력]

첫째 줄에는 이들이 만나는 시간을, 둘째 줄에는 1분도 쉬지 않고 달려야 하는 도로의 수(= 임계 경로에 포함되는 도로의 수)가 몇 개인지 출력하여라.

 

[아이디어]

1) 처음엔 위상정렬을 해야한다는 생각을 못했다. dfs를 통해 도착지에 도달하는 경우의 수를 구하되, weight의 최댓값을 업데이트 하면서 최대일 때만 경로까지 구해내도록 구현했으나, 시간초과가 발생했다. (아래 첫 번째 코드)

2) 비용이 최대인 경우만 선택적으로 탐색하는 것이 아닌, 모든 케이스를 다루기도 하고, dfs와 백트래킹을 함께 구현한 탓에 불필요한 방문과 빠져나오는 연산이 반복되면서 1)의 문제가 발생하는 듯 하다.

3) 위상정렬을 이용하면 각 노드에 도달할 수 있는 최대 비용의 경로를 저장해둘 수 있고, 이를 이용하면 도착지에서 출발지로 돌아오면서 비용이 최대인 경우만을 선택적으로 탐색할 수 있다. (다른 블로그 코드 참고)

4) e에서 s로 bfs를 통해 돌아가면서 방문하는 모든 노드 x에 대해 x에 도달하는 최대 비용을 발생하게 하는 간선이 맞는지을 때에만 해당 간선을 센다면 중복의 우려 없이 임계 경로에 포함되는 모든 간선을 셀 수 있다. 

 

# 시간 초과
from collections import deque
n=int(input())
m=int(input())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
s,e=map(int,input().split())
stack = deque([s])
visit = [0]*(n+1)
visit[s]=1
ans = []
max_ = 0
def f(stack,visit,weight,e):
    global max_
    k = stack[-1]
    if k==e:
        if max_==weight:
            ans.append(stack.copy())
        elif max_ < weight:
            max_ = weight
            ans.clear()
            ans.append(stack.copy())
        return
    for x,w in g[k]:
        if not visit[x]:
            visit[x]=1
            stack.append(x)
            f(stack,visit,weight+w,e)
            visit[x]=0
            stack.pop()

f(stack,visit,0,e)
print(max_)
a=set()
for y in ans:
    for i in range(len(y)-1):
        a.add((y[i],y[i+1]))
print(len(a))

import sys
input=sys.stdin.readline
from collections import deque
n=int(input()) 
m=int(input()) 
g=[[]*(n+1) for _ in range(n+1)]
back=[[]*(n+1) for _ in range(n+1)]
d=[0]*(n+1) 
w=[0]*(n+1)
v=[0]*(n+1)
for _ in range(m):
    a,b,t=map(int,input().split())
    g[a].append((b,t))
    back[b].append((a,t))
    d[b]+=1
s,e=map(int,input().split())
q=deque([s])
while q:
    cur=q.popleft()
    for i,t in g[cur]:
        d[i]-=1
        w[i]=max(w[i],w[cur]+t)
        if d[i]==0:
            q.append(i)
cnt=0 
q.append(e)
while q: 
    cur=q.popleft()
    for i,t in back[cur]:
        if w[cur]-w[i]==t:
            cnt+=1
            if v[i]==0:
                q.append(i)
                v[i]=1
print(w[e])
print(cnt)

빡고수의 코드 앞에 어김 없이 작아진다,,, 나는 언제쯤 ㅎㅎ.. 그래도 위상 정렬을 이용하면 임계 경로에 쉽게 접근할 수 있음을 새로 알았다!