[BOJ] 파이썬 2307번_도로검문 파이썬

문제 링크: https://www.acmicpc.net/problem/2307

풀이

import heapq
import sys, math
inf = math.inf
input = lambda:sys.stdin.readline().strip()

n, m = map(int,input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    s,e,c = map(int,input().split())
    graph[s].append([e, c])
    graph[e].append([s, c])

def trav(start, blocked_edge):
    queue = []
    visited = [False for _ in range(n+1)]
    distance = [inf for _ in range(n+1)]

    s, e = blocked_edge
    router = []

    heapq.heappush(queue,(0,start, [start]))
    distance[start] = 0
    while queue:
        current_cost, current, path = heapq.heappop(queue)

        if visited[current]:
            continue
        if current == n:
            router = path
        visited[current] = True
        for next, next_cost in graph[current]:
            if not visited[next] and distance[next] > distance[current] + next_cost:
                if (current == s and next == e) or (current == e and next == s):
                    continue
                distance[next] = distance[current] + next_cost
                heapq.heappush(queue, (distance[next], next, path + [next]))


    return distance, router

origin_time,router = trav(1, (0,0))

res = []
toBlock = []
if origin_time[n] == inf:
    print(-1)
    sys.exit()
for i in range(len(router) - 1):
    toBlock.append((router[i], router[i + 1]))

for edge in toBlock:
    temp = trav(1, edge)[0][n]
    res.append(temp)

res = max(res) - origin_time[n]


if res == inf:
    print(-1)
else:
    print(res)

항상 양의 정수를 가진 그래프에서 최단거리를 계산하는 문제이므로 다익스트라 알고리즘을 사용한다.

우선 아무런 엣지도 검문하지 않을 경우의 최단경로를 구해준다.

이문제의 핵심은 도로검문을 할 (비활성화시킬) 엣지를 어떻게 선정하느냐이다.

모든 엣지를 각가 한번씩 뺀 경우를 모두 다익스트라 알고리즘을 돌린다면 5000 ^ 2 * 10 정도이므로 시간초과가 날 것이기 때문이다.

생각해보면, 검문시킬 엣지는 원래의 최단경로를 잇는 엣지들만 검문하면 된다. 원래 최단경로에 포함되는 엣지들을 막는것이 지연시킬 수 있는 시간을 최대화 할 수 있기 때문이다.

따라서, 아무런 엣지도 검문하지 않을 경우의 최단경로를 구할 때, 경로에 포함되는 엣지들도 같이 구해낸 후 포함된 엣지들을 각각 한번씩 제외하면서 다익스트라를 돌린 후 결과를 계산하면 된다.