BOJ - 13424

백준 문제 링크
비밀 모임

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. distance를 returng하는 기본 다익스트라 함수를 만들어준다.
3. 그 후 비밀통로의 정보를 graph에 갱신해주고,
   친구의 수 k와 친구들이 있는 방 room을 받아준다.
4. 이제 친구들이 있는 방에서 가장 가까운 방이 어디인지찾아봐야한다.
   answer = [INF] * (n + 1)로 만들어 준다.
   -> 여기에 이동 거리의 합을 넣을 것이다.
   i를 1부터 n + 1 까지 증가시키면서
   dist = dijkstra(i) 로 지정한다.
   answer[i] = sum(dist[f] for f in room) 으로
   친구들이 있는 방 까지의 거리를 다 더해준다.

• 위의 코드는
  answer[1] = ( 1 -> 4 + 1 -> 5 )
  answer[2] = ( 2 -> 4 + 2 -> 5 ) 이런 의미인 것이다.

5. 마지막으로 최솟값의 인덱스를 answer에서 찾아내 출력하면 끝!

👌🏻코드

import heapq
T = int(input())

INF = int(1e9)

def dijkstra(start):
        distance = [INF] * (n + 1)
        
        q = []
        heapq.heappush(q, (0, start))
        distance[start] = 0
        
        while q:
            dist, now = heapq.heappop(q)
            
            if distance[now] < dist:
                continue
                
            for i in graph[now]:
                cost = dist + i[1]
                
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
                    
        return distance
    

for _ in range(T):
    
    n, m = map(int, input().split())
    
    graph = [[] for _ in range(n + 1)]
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
        
    k = int(input()) # 친구의 수 
    room = list(map(int, input().split())) # 친구들이 현재 위치한 방
    
    answer = [INF] * (n + 1)

    for i in range(1, n + 1):
        dist = dijkstra(i) # i번 방에서 각 방 까지의 거리 
        answer[i] = sum(dist[j] for j in room) # 친구들이 현재 위치한 방 까지의 거리
    print(answer.index(min(answer))) # 친구들의 이동 거리 총합이 최소가 되는 방의 번호