[백준] 17835번: 면접보는 승범이네

📌 문제

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

📌 설명

주어진 노드로부터 특정 노드들까지의 최단 거리를 구하고, 최단 거리 중 최댓값을 구하는 문제이다. 다익스트라 알고리즘을 통해 시작 노드로부터 각 노드까지의 최단 경로를 구할 수 있으므로, 각 노드에 대해 다익스트라 알고리즘을 적용한 후, 면접장까지의 거리 중 최단 거리를 선택하고, 모든 노드에 대하여 산출된 최단 거리 중 최댓값을 구하면 된다.

과연 이 방법이 잘 동작할까? 이론 상 잘 동작한다. 그러나 시간 초과가 발생한다. 우선순위 큐를 통해 다익스트라 알고리즘을 구현하는 경우 시간복잡도는 $O(ElogV)$이다. 이를 모든 노드에 대해 수행하므로 전체 시간복잡도는 $O(V*ElogV)$가 되며, 문제의 제한을 아득히 넘어가게 된다. 우리는 각 노드로부터 면접장까지의 거리만 구하면 되는데, 필요 없는 제 3의 노드까지의 최단 거리를 구하기 때문이다.

어차피 특정 노드에서 면접장까지 향하는 경로의 최소 거리나, 면접장부터 특정 노드까지 향하는 경로의 최소 거리나 같다. 따라서 우린 면접장에서부터 각 노드까지의 최단 거리를 구함으로써 효율적으로 답을 구할 수 있다. 이를 구현하기 위해 역방향 그래프를 이용하며, 면접장들을 시작 노드로 삼는다. 이 방법은 다익스트라 알고리즘을 단 한 번만 수행하여 원하는 답을 찾을 수 있다.

참고로 시작 노드가 여러 개 존재하는 다익스트라 알고리즘을 multi source dijkstra 알고리즘이라고 부른다. 기존의 다익스트라 알고리즘 동작과 동일하며, 초기에 시작 노드를 초기화 및 우선순위 큐에 삽입하는 부분만 다르다.

비록 $K$개의 시작 노드가 존재하지만, 단순 다익스트라 알고리즘이므로 전체 시간복잡도는 $O(MlogN)$이다.

graph 에서 각 노드마다 인접 노드 정보를 저장하므로 총 공간복잡도는 $O(N+M)$, dist 배열은 $O(N)$, 우선순위 큐는 최대 $O(M)$, start 에는 $O(K)$ 이다. 총합은 $O(N+M+K)$이나, $K \leq N$이므로 전체 공간복잡도는 $O(N+M)$이다.

📌 코드

import sys
import heapq

input=sys.stdin.readline

# 도시의 수, 도로의 수, 면접장의 수
n,m,k=map(int,input().split())

graph=[[] for _ in range(n+1)]

# 면접장을 시작 노드로 역방향으로 다익스트라 알고리즘을 적용한다.
for _ in range(m):
    u,v,c=map(int,input().split())
    graph[v].append((c,u))

q=[]
dist=[sys.maxsize]*(n+1)
start=list(map(int,input().split()))
for s in start:
    dist[s]=0
    heapq.heappush(q,(0,s))

max_dist=-1
city=-1

while q:
    w,cur=heapq.heappop(q)

    if dist[cur]<w:
        continue

    for nw,nxt in graph[cur]:
        if w+nw<dist[nxt]:
            dist[nxt]=w+nw
            heapq.heappush(q,(dist[nxt],nxt))

for i in range(1,n+1):
    if dist[i]!=sys.maxsize and dist[i]>max_dist:
        max_dist=dist[i]
        city=i

print(city)
print(max_dist)