⚠️ 문제
- https://www.acmicpc.net/problem/2307
🔐 풀이
이 문제는 다익스트라 알고리즘을 통해 해결할 수 있었습니다.
경찰이 도로를 막아 용의자의 탈출을 최대한 지연시켜야 하고, 지연 시간을 구하기 위해서는 우선 용의자의 가장 빠른 탈출 시간을 구해야합니다.
첫번째로 다익스트라 알고리즘을 통해 용의자의 가장 빠른 탈출 시간 (최단 거리)를 구한 이후, 경찰이 검문할 수 있는 도로를 하나씩 선택하여 제외하고 최단 거리를 구해 앞서 구한 최단 탈출 시간과 비교하려 했으나 시간 초과가 발생했고 검문할 도로를 선택하는 방법을 다르게 해야겠다고 생각했습니다.
이에 생각한 방법은 가장 처음 구했던 용의자의 가장 빠른 탈출 시간의 경로 중의 한 도로를 선택해 검문하는 방법입니다.
생각해보면, 용의자의 가장 빠른 탈출 시간 경로가 아닌 다른 경로를 경찰이 검문했을 경우 용의자는 원래 최단 경로를 통해 탈출하면 그대로 최단 시간에 탈출할 수 있게 됩니다.
그러므로 경찰은 용의자의 최단 경로 중 한 곳에 검문을 실시해야 탈출 시간에 영향을 줄 수 있을 것이라 생각해 처음 용의자의 가장 빠른 탈출 경로를 저장해두고, 이 경로를 하나씩 선택해 검문을 실시해보는 방식으로 진행했습니다.
🧑🏻💻 코드
import sys
import heapq
INF = int(1e9)
N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
a, b, t = map(int, sys.stdin.readline().split())
graph[a].append((t, b))
graph[b].append((t, a))
path = [INF for _ in range(N+1)]
def dijkstra(block_first, block_second):
dist = [INF for _ in range(N+1)]
dist[1] = 0
q = []
heapq.heappush(q, (0, 1))
while q:
distance, now = heapq.heappop(q)
if now == N:
break
if distance > dist[now]:
continue
for near in graph[now]:
# block_first, block_second는 경찰이 검문을 실시하는 도로의 출발, 도착 두 지점
if (block_first == now and block_second == near[1]) or (block_first == near[1] and block_second == now):
continue
if distance + near[0] < dist[near[1]]:
dist[near[1]] = distance + near[0]
# 가장 처음 dijkstra에서 용의자의 최단 경로를 구할 때 경로 저장
if block_first == INF:
path[near[1]] = now
heapq.heappush(q, (dist[near[1]], near[1]))
return dist[N]
# 용의자의 가장 빠른 탈출 시간 저장
shortest = dijkstra(INF, INF)
result = -1
for idx in range(N, 1, -1):
# 용의자의 가장 빠른 탈출 경로에 포함된 도로만 검문
if path[idx] != INF:
blocked_dist = dijkstra(idx, path[idx])
if blocked_dist == INF:
result = -1
break
else:
difference = blocked_dist - shortest
result = max(difference, result)
print(result)