[BOJ][Python] 백준 13424번 : 비밀 모임(다익스트라)

- 문제 링크

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

13424번: 비밀 모임

- 풀이

거의 기본 다익스트라 문제였다. 마지막 부분에 조금 헤맸지만 그래도 맞혔다.

 

 1. 지문에서도 양방향 통행이 가능하다고 했기 때문에 그래프를 양방향 그래프로 만들어 준다. 

 

 2. 다익스트라 함수에서 별 다른 특이사항은 없다. 그냥 다익스트라 함수 원형을 구현해주면 된다. 거리 배열인 distance 배열을 return 해주면 된다.

 

 3. 이제 for문을 도는데, list 형태로 받은 방의 번호를 가지고 반복한다. 각 방의 번호로 다익스트라 함수를 실행한다.

 

 4. 다익스트라 함수를 통해 distance 배열이 return 됐을텐데, distance 배열의 길이만큼 for문을 돌면서 결과값을 담을 배열에 값을 하나하나씩 값을 삼입한다.

 

 5. 방의 번호만큼 for문을 돌았다면, 결과값이 담겨있는 배열 중에서 제일 작은 값의 위치를 출력해주면 된다.

 

- 코드

import sys
import heapq
input = sys.stdin.readline
INF = int(1e10)

def dijkstra(start):
    queue = []
    distance = [INF] * (N+1)
    distance[start] = 0
    heapq.heappush(queue, (0, start))
    while queue:
        dist, curr = heapq.heappop(queue)
        if dist > distance[curr]:
            continue
        
        for next, weight in graph[curr]:
            cost = dist + weight
            if cost < distance[next]:
                distance[next] = cost
                heapq.heappush(queue, (cost, next))
    return distance

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    arr = [0] * (N+1)
    graph = [[] for _ in range(N+1)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    K = int(input())
    A = list(map(int, input().split()))
    
    for i in A:
        res = dijkstra(i)
        for j in range(len(res)):
            arr[j] += res[j]

    print(arr.index(min(arr)))