문제 내용

• 도시의 수 N(2<=N<=100,000), 면접장의 수 K(1<=K<=N)
• 각각의 면접자들이 면접장을 찾아가는 최단 거리의 최댓값을 구하는 문제
• 다익스트라 알고리즘, N명의 면접자들마다 면접장까지의 거리를 예측하도록 함정을 파놓은 것으로 느껴짐 -> 백프로 시간초과 유도

처음 떠오른 아이디어

• 앞서 해결했던 문제 중, 1(출발점) -> N(도착점)으로 가는 특정 문제를 해결하는 것을 반대로, N(도착점)에서 나머지들 전체로 가는 문제가 있었다. 해당 문제를 해결하기 위해서, 생각했던 아이디어는 A -> B의 대응관계로 주어진 Edge들을 거꾸로 뒤집어서 A <- B 로 대응시킨 뒤에 N 에서 나머지들로의 최단거리를 구하면, 결국 한번에 해결해낼 수 있는 것이라는 방법론을 이용해 해결했다.
• 또한 앞서 시간초과를 해결하기 위해서, 다익스트라 알고리즘을 heapq를 사용, 방문한 노드는 heaqp에 추가하지 않도록 하여 높은 시간 효율성을 챙길 수 있었다.
• 여기서도 그 생각을 통해 문제를 쉽게 해결할 수 있을 것이라고 짐작했다.

첫 제출

• 위에서 말한 효율적인 다익스트라 사용, 전체 인터뷰장에서 각 도시에 대한 최단거리를 모두 구한 후에 비교하여, 최단 거리를 구하고, 그 중 최대인 거리를 구하는 방식으로 문제를 해결하였다.

    total_distance = [] # 인터뷰장 전체에 대한 각 도시까지의 거리 저장
    for i in range(K):
        total_distance.append(dijkstra(interviews[i], edges)) # 다익스트라 수행
  
    max_distance = -1
    max_i = 0
    for i in range(1, N + 1):
        tmp = []
        for k in range(K):
            tmp.append(total_distance[k][i]) # 각 인터뷰장까지에 대한 해당 도시의 거리 추가
        min_tmp = min(tmp) # 최단거리 구하기
        if max_distance < min_tmp: # 그 중 최대를 구하기 위해서
            max_distance = min_tmp
            max_i = i
  

• 역시 광탈… 1%에서 시간초과를 맞이해버렸다.

두번째 제출

• 공통인 거리 배열을 사용해서, 모든 인터뷰 장에서의 출발은 거리를 0으로 두고 시작한다면, 한번의 반복으로 구해낼 수 있을 것이라고 생각했다.

    def dijkstra(start, edges):
        global dist
    ...
    dist = [float('inf')] * (N + 1)
    for i in range(K):
        dijkstra(interviews[i], edges)
  

• 시간 초과… 당연히 최악의 경우에 O(N*Mlog(N))이 될 수 있기에, 이렇게 해결하면 안됐다.
• 근데 이 아이디어 괜찮아보였다. 모든 인터뷰 장에서의 출발은 거리를 0으로 두고 시작 이 방법을 다익스트라 한번으로 풀어볼 수 있을 것 같았다.

세번째 제출

• 다익스트르 수행 처음에 거리배열을 INF로 초기화 해주고, 탐색 시작 노드의 거리를 0으로 변경해준다. 그럼 이 작업에서, 인터뷰 장 전체의 거리를 0으로 변경해주고 나서 다익스트라를 수행해보면 어떨까?

    def dijkstra(interview_city, edges):
        heap = []
        dist = [float('inf')] * (N + 1)
        visited = [False] * (N + 1)
  
        for t in interview_city:
            heapq.heappush(heap, (0, t))
            dist[t] = 0
            visited[t] = True
  

• 드디어 시간초과의 늪에서 탈출했다..

전체 코드

from collections import defaultdict
import heapq

def dijkstra(interview_city, edges):
    heap = []
    dist = [float('inf')] * (N + 1)
    visited = [False] * (N + 1)

    for t in interview_city:
        heapq.heappush(heap, (0, t))
        dist[t] = 0
        visited[t] = True
        
    while heap:
        c, v = heapq.heappop(heap)
        if dist[v] < c and visited[v]:
            continue
        visited[v] = True
        for nc, nv in edges[v]:
            if dist[nv] > c + nc:
                dist[nv] = c + nc
                if not visited[nv]:
                    heapq.heappush(heap, (c + nc, nv))
    return dist
    
N, M, K = map(int, input().split())
edges = defaultdict(list)

for _ in range(M):
    U, V, C = map(int, input().split())
    edges[V].append((C, U))
interviews = list(map(int, input().split()))

res = dijkstra(interviews, edges)
max_distance = -1
max_i = 0
for i in range(1, N + 1):
    if res[i] > max_distance:
        max_distance = res[i]
        max_i = i

print(max_i)
print(max_distance)

후기

• 어려웠다.. 쉽다고 생각했는데 어려웠다.
• 기본 알고리즘에서 조금의 변주를 주면, 찾는데 시간이 참 오래 걸리는 것 같다.
• 다익스트라 외에도 플로이드-와샬 알고리즘도 한번 전체적으로 정리하는 시간을 가져야 할 것 같다.