다익스트라 응용하기 - 시작 정점은 여러개일 수도 있다

1. 문제

 

14221번: 편의점 (acmicpc.net)

14221번: 편의점

 

2. 풀이

 

집에서 편의점까지 거리가 가장 가까운, 집의 번호를 출력하는 문제다.

 

간단하게 생각하면, 집이 p개 있고 편의점이 q개 있는데.. 

 

p개의 점 각각에 대하여, 다익스트라 알고리즘을 수행하면 p개의 다익스트라 배열이 나오고..

 

여기서 편의점 q개의 점에 대해 거리를 구해보고 거리가 가장 가까운 점을 찾으면 될것이다

 

근데 이렇게 하면 다익스트라를 p번이나 수행해야하고, 각각에 대해 q번이나 순회하니 시간복잡도가 크다

 

-----------------------------------------------------------------------------------------------------

 

반대로 생각해서.. 편의점에서 시작한다면 어떨까?

 

그리고 한번 더 생각해서.. 편의점 하나에서만 다익스트라 알고리즘을 수행하는 것이 아니라, 

 

편의점 후보들 모두에서 한번에 다익스트라 알고리즘을 수행하는 것이다.

 

이게 왜 가능할까

 

편의점 정점들이 서로 구별되는 고유한 정점이 아니라,

 

문제 자체가 "집의 여러 후보들에 대하여, 존재하는 편의점과 거리가 가까운 집"을 찾는 것이기 때문에,

 

"어떤 특정 편의점"과 거리가 가까운 집을 찾는 것이 아니라, 불특정 편의점들 중에서 거리가 가까운 집을 찾는 것이기 때문이다.

 

----------------------------------------------------------------------------------------------------

 

그러면 "편의점 후보들 모두에서 한번에 다익스트라 알고리즘"을 수행하는 것은 어떻게 할 수 있을까

 

매우 간단하다

 

다익스트라 함수에서, 시작할때 우선순위 큐에 편의점 정점들을 모두 거리가 0인 채로 넣고 시작하면 된다

 

그러면 다익스트라 알고리즘을 반복적으로 수행하면서.. 편의점에서 나머지 정점들 사이 최단 거리가 갱신될건데..

 

편의점은 s1,s2,...,sq로 q개가 있다고 한다면...

 

반복문이 계속 돌면서.. 어떤 집 정점 p와의 거리가 s1 - p 사이 거리가 a로 최단 거리였는데...

 

s2 - p 사이 거리가 a > b로 더 짧았다면.. distance[p] = b로 갱신될거다..

 

마찬가지로, s3 - p 사이 거리가 b > c로 더 짧았다면.. distance[p] = c로 갱신될거고..

 

이게 계속 돌면서..

 

distance[p]에는..? s1,s2,...,sq와 p사이 거리 중 가장 짧은 거리가 들어가게 될 것이다.

 

import heapq
from sys import stdin

INF = 10000000000000000000000000000

def dijkstra(store,n):
    
    q = []

    distance = [INF]*(n+1)
    
    #모든 편의점 정점들을 우선순위 큐에 넣는다.
    #모든 편의점 정점들이 출발 정점이 되고, 거리는 모두 0이 된다.
    for s in store:
        
        heapq.heappush(q,(0,s))
        distance[s] = 0
    
    #다익스트라 알고리즘을 수행하면서,
    #모든 편의점 정점들에 대하여, 가장 거리가 짧은 경우가 distance에 기록될 것
    while q:
        
        dist,u = heapq.heappop(q)

        if distance[u] < dist:
            
            continue
        
        for b,c in graph[u]:
            
            cost = dist + c

            if distance[b] > cost:
                
                distance[b] = cost
                heapq.heappush(q,(cost,b))
    
    return distance

n,m = map(int,stdin.readline().split())

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

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    graph[a].append((b,c))
    graph[b].append((a,c))

p,q = map(int,stdin.readline().split())

house = list(map(int,stdin.readline().split()))
store = list(map(int,stdin.readline().split()))

answer = INF+1
min_h = n+1

dist = dijkstra(store,n)

#편의점과 최단거리가 같은 경우, 더 작은 번호의 정점을 출력하기 위해
house.sort()

#집 후보들을 순회해서, 편의점과 최단 거리를 비교
for h in house:
    
    if dist[h] == INF:
        
        continue
    
    if answer > dist[h]:
        
        answer = dist[h]
        min_h = h #house를 정렬해놔서, 이 순간에 기록되는 정점 번호가 결국에 가장 작은 번호의 정점

print(min_h)