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

문제

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

분석

도시 정보와 면접장이 배치된 도시가 주어질 때, 면접장까지의 거리가 가장 먼 도시와 그 거리를 구하는 문제이다.

최소거리를 구하는 다익스트라문제이다. 그러나 모든 경우에 대해서 다익스트라를 진행하기에는 N이 최대 100,000이므로 시간을 줄이는 방법을 생각해야 한다.

처음으로 생각할 것이 주어진 정보를 역방향으로 바꾸어 면접장에서 다른 도시들로의 거리로 바꾸는 것이다. 그리고 면접장이 위치한 도시들을 먼저 우선순위큐에 넣고 다익스트라 알고리즘을 진행하면 한 번의 알고리즘 적용으로 모든 거리 배열을 채울 수 있다.

거리배열을 구하고 나면 그중 최대인 값과 인덱스 값을 얻기는 쉽다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from heapq import heappush, heappop
INF = sys.maxsize
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((u, c))
position = list(map(int, input().split()))

def dijkstra():
    dist = [INF]*(n+1)
    pq = []
    for i in position:
        dist[i] = 0
        heappush(pq, (0, i))
    while pq:
        now_d, now = heappop(pq)
        if dist[now] < now_d:
            continue
        for nxt, nxt_d in graph[now]:
            if dist[nxt] > now_d+nxt_d:
                dist[nxt] = now_d+nxt_d
                heappush(pq, (now_d+nxt_d, nxt))
    return dist

result = dijkstra()
mx, mx_city = 0, 0
for i in range(1, n+1):
    if mx < result[i]:
        mx = result[i]
        mx_city = i
print(mx_city)    
print(mx)

끝으로..

다익스트라 알고리즘을 활용한 문제를 풀어봤다.