[python] 백준 17835 :: 면접보는 승범이네 (dijkstra)

면접보는 승범이네

# 문제
마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.

면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.

모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '면접장까지의 거리'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.

속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.

승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.

# 입력
첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다.

다음 M개의 줄에 걸쳐 한 줄마다 도시의 번호 U, V(U ≠ V)와 도로의 길이 C(1 ≤ C ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 U에서 V로 갈 수 있는 도로가 존재하고, 그 거리가 C라는 뜻이다.

마지막 줄에 면접장이 배치된 도시의 번호 K개가 공백을 두고 주어진다.

# 출력
첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.

둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.

모든 도시에서 출발해서 모든 도시로 도착하는 다익스트라 방식으로 풀었더니 시간초과가 발생했다ㅠ^ㅠ

시간 초과가 발생하는 이유

이 문제에서 도시의 개수만큼 다익스트라를 수행하면
최악의 경우, 다익스트라의 시간 복잡도인 $ElogV$에 도시의 최대 개수인 100,000을 곱한 수인 880,482,000번 연산을 하게 된다.
👉🏻 모든 경우의 수를 연산하면 시간 초과가 발생한다.
따라서 모든 도시에서 시작하는 방법은 사용할 수 없다.

풀이 방법

모든 도시에서 면접장으로 갈 수 있는 경로가 항상 있다고 주어졌으므로,
반대로 면접장에서 도시로 향하는 방향으로 다익스트라를 수행할 수 있다.
그러기 위해서는 도시의 연결 정보를 입력받을 때 역방향으로 관계를 지정해줘야 한다.
(반대로 탐색을 해나갈 것이기 때문!)
도시의 정보는 arr에, 면접장 정보는 targets에 담아주었다.

arr = [[] for _ in range(N+1)]
for i in range(M):
    a, b, cost = map(int, sys.stdin.readline().split())
    arr[b].append([a, cost])

targets = list(map(int, sys.stdin.readline().split()))

다익스트라에서 탐색을 할 도시 리스트 h에 각 면접장을 모두 넣어주고 시작한다.

def dijkstra():
    h = []
    for t in targets:
        heapq.heappush(h, [0, t])
        result[t] = 0

최단 경로를 탐색할 때는 각 도시에 대한 최단 거리 정보가 이미 갱신되어 현재 비용보다 적다면 수행하지 않아야 한다.
이것도 해주지 않으면 시간 초과가 발생하는데,
모든 도시와 모든 도시가 연결된 경우를 생각하면 분기를 해줘야 함을 알 수 있다.

    while h:
        cost, city = heapq.heappop(h)
        if result[city] < cost:
            continue

이후에는 다익스트라를 이어서 수행한다.

        for next_city, next_cost in arr[city]:
            if cost + next_cost < result[next_city]:
                result[next_city] = cost+next_cost
                heapq.heappush(h, [cost+next_cost, next_city])

전체 코드

import sys
import heapq
N, M, K = map(int, sys.stdin.readline().split())
arr = [[] for _ in range(N+1)]
for i in range(M):
    a, b, cost = map(int, sys.stdin.readline().split())
    arr[b].append([a, cost])

targets = list(map(int, sys.stdin.readline().split()))


def dijkstra():
    h = []
    for t in targets:
        heapq.heappush(h, [0, t])
        result[t] = 0
    while h:
        cost, city = heapq.heappop(h)
        if result[city] < cost:
            continue
        for next_city, next_cost in arr[city]:
            if cost + next_cost < result[next_city]:
                result[next_city] = cost+next_cost
                heapq.heappush(h, [cost+next_cost, next_city])


max_start, max_cost = 0, 0
result = [int(1e11)] * (N+1)
dijkstra()
for i, r in enumerate(result):
    if r > max_cost and r != int(1e11):
        max_start, max_cost = i, r
print(max_start)
print(max_cost)