[백준] 1948. 임계경로 - Python — 젝무의 개발새발

[Platinum V]

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

1948번: 임계경로

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의

www.acmicpc.net

풀이 1 (오답)

문제를 보자마자, 그냥 크게 생각하지 않고 DFS(혹은 BFS..?) 느낌? 그냥 그래프 탐색으로 풀어본 결과.

MLE가 나오긴 했지만, 다시 보니 지난 거리 개수를 셀 때 중복을 허용했기 때문에 틀린 코드다.

MLE. (메모리 초과) / WA.

from collections import deque
n = int(input())
m = int(input())

graph = dict(zip([i for i in range(1, n+1)], [[] for _ in range(n)]))
time = [[0]*(n+1) for _ in range(n+1)]

# Input
for _ in range(m):
    a, b, t = map(int, input().split())
    graph[a].append(b)
    time[a][b] = t

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

# (도시, 걸린시간, 지난거리개수)
max_time = 0
road_cnt = 0
deq = deque([(start, 0, 0)])
while deq:
    c, t, r = deq.popleft()
    for city in graph[c]:
        deq.append((city, t + time[c][city], r + 1))
    
    if c == end:
        if max_time == t:
            road_cnt += r
        elif max_time < t:
            max_time = t
            road_cnt = r
        
print(max_time)
print(road_cnt)

풀이 2 (오답, 풀이 포함)

Topological Sort(위상 정렬)을 통 우선 목적지까지의 최대 도달 시간을 구한다.

각 도시(정점)에서의 진입 차수(indegree) 를 따져가며, 모든 연결되는 진입 경로를 탐색할 때까지 기다리며,

그 도시에 도착할 수 있는 최대의 시간을 구한다.

그 이후 다시 그 도시에서 진출할 수 있는 경로들에 대해 queue에 enqueue하며 반복하고,

그렇게 목적지에서의 최대 도달 시간을 구할 수 있다.

(line 25~34)

유향 비순환 그래프(DAG)이기 때문에, 각 도시의 최대 도달 시간만 구하며 진행해도 목적지에서의 최대 도달 시간을 구함이 보장된다.

최대 도달 시간을 구한 이후에는, 목적지부터 다시 되돌아가며, 최대 도달 시간을 만들어내는 경로들을 구한다.

거꾸로 돌아가며, 지금 현재 체크하는 경로가 s -> e 일 때,

(e에서의 최대 도달 시간) - (s -> e 경로에 걸리는 시간) = (s에서의 최대 도달 시간) 이라면, 최대 도달 시간을 달성하는 경로의 일부인 도로이므로, 그런 것들을 체크하고 queue에 넣어가며 진행한다. (주석 참고)

(line 40~52)

그러나 4n% 쯤에서 MLE. (메모리 초과)

from collections import deque
n = int(input())
m = int(input())

# Topological Sort Setting & Time
graph_in_cnt = dict(zip([i for i in range(1, n+1)], [0 for _ in range(n)]))
graph_in = dict(zip([i for i in range(1, n+1)], [[] for _ in range(n)]))
graph_out = dict(zip([i for i in range(1, n+1)], [[] for _ in range(n)]))
time = [[0]*(n+1) for _ in range(n+1)]

# Input
for _ in range(m):
    a, b, t = map(int, input().split())
    graph_in[b].append(a)
    graph_out[a].append(b)
    graph_in_cnt[b] += 1
    time[a][b] = t
    
start, end = map(int, input().split())

# 도시별 최대 시간
max_time = [0]*(n+1)

# Topological Sort
deq = deque([start])
while deq:
    s = deq.popleft()
    
    for e in graph_out[s]:
        graph_in_cnt[e] -= 1
        # 도시별 최대 도달 시간 갱신
        max_time[e] = max(max_time[e], max_time[s] + time[s][e])
        if graph_in_cnt[e] == 0:
            deq.append(e)

# 목적지에서의 최대 도달 시간은 도시마다의 최대 도달 시간으로만 구성해도 구할 수 있다!
print(max_time[end])

# BackTracking
deq = deque([end])
while deq:
    e = deq.popleft()
    
    # 거꾸로 되돌아가면서, 지금 보는 경로가 s -> e일 때,
    # (e에서의 최대 도달 시간) - (s -> e 경로에 걸리는 시간) = (s에서의 최대 도달 시간) 이라면,
    # (그러니까, max_time[e] - time[s][e] == max_time[s] 라면,)
    # 카운팅할 경로에 추가! (최대 시간이 걸리는 경로임!)
    for s in graph_in[e]:
        if max_time[e] - time[s][e] == max_time[s]:
            deq.append(s)
            # time[e][s]는 모두 0으로 초기화되어 있고, 쓸 일이 없으므로, 메모리 낭비 없이 중복 제거를 위해 time 2차원 배열을 재사용.
            time[e][s] = -1

roadCnt = 0
for i in range(n+1):
    for j in range(n+1):
        if time[i][j] == -1:
            roadCnt += 1
print(roadCnt)

풀이 3 (정답, 풀이 2 최적화)

O(N^2)의 Space Complexity를 갖던 time 2차원 배열을 삭제시키고, topological sort에 이용하는 2차원 배열에 시간 값을 같이 저장하도록 했다.

(topological sort에 사용하는 2차원 배열은 도로 수의 영향을 받아 최대 100,000개 정도이지만, time 2차원 배열은 도시 수에 영향을 받아 10,000*10,000 의 공간을 차지.)

또한, Backtracking을 할 때에도 이미 지나간 곳을 visited 체크해주며 건너뛰어도 조건에 맞는 모든 도로를 체크할 수 있다는 것이 보장되기에, 그렇게 수정하였다.

(사실 이것저것 굉장히 최적화를 많이 시도하였다.)

AC.

from collections import deque
n = int(input())
m = int(input())

# Topological Sort Setting & Time
graph_in_cnt = [0 for _ in range(n+1)]
graph_in = [[] for _ in range(n+1)]
graph_out = [[] for _ in range(n+1)]

# Input
for _ in range(m):
    a, b, t = map(int, input().split())
    graph_in[b].append((a, t))
    graph_out[a].append((b, t))
    graph_in_cnt[b] += 1
    
start, end = map(int, input().split())

# 도시별 최대 시간
max_time = [0]*(n+1)

# Topological Sort
deq = deque([start])
while deq:
    s = deq.popleft()
    
    for e, t in graph_out[s]:
        graph_in_cnt[e] -= 1
        # 도시별 최대 도달 시간 갱신
        max_time[e] = max(max_time[e], max_time[s] + t)
        if graph_in_cnt[e] == 0:
            deq.append(e)

# 목적지에서의 최대 도달 시간은 도시마다의 최대 도달 시간으로만 구성해도 구할 수 있다!
print(max_time[end])

# BackTracking
result = 0
visited = [False for _ in range(n+1)]
deq = deque([end])
while deq:
    e = deq.popleft()
    
    # 거꾸로 되돌아가면서, 지금 보는 경로가 s -> e일 때,
    # (e에서의 최대 도달 시간) - (s -> e 경로에 걸리는 시간) = (s에서의 최대 도달 시간) 이라면,
    # (그러니까, max_time[e] - time[s][e] == max_time[s] 라면,)
    # 카운팅할 경로에 추가! (최대 시간이 걸리는 경로임!)
    for s, t in graph_in[e]:
        if max_time[e] - t == max_time[s]:
            result += 1
            
            # 중복 제거
            if not visited[s]:
                deq.append(s)
                visited[s] = True

print(result)

풀이 1 (오답)

풀이 2 (오답, 풀이 포함)

풀이 3 (정답, 풀이 2 최적화)

티스토리툴바