[백준/Python] 13424번 비밀 모임

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

13424번: 비밀 모임

 

문제분석

1. 분류
   • 그래프 이론, 다익스트라, 플로이드-워셜
2. 문제설명
   • N개의 방, M개의 비밀통로, K명의 친구들
   • 모임에 참여하는 친구들은 N개의 방 중에서 한 군데씩에 각각 위치해있다.
   • 이들은 항상 처음 위치에서 모임 장소까지의 이동 거리가 가장 짧은 경로만을 이용한다.
   • 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용한다.
   • 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소를 찾아 출력하는 프로그램을 작성한다.

 

코드

from heapq import *

import sys

input = sys.stdin.readline

def dijkstra(s):

cost = [float('inf')] * (n+1)

hq = [[0, s]]

cost[s] = 0

while hq:

t,x = heappop(hq)

if cost[x] != t: continue

for nx, nt in adj[x]:

if cost[nx] > t+nt:

cost[nx] = t+nt

heappush(hq, [cost[nx], nx])

return cost

t = int(input())

for _ in range(t):

n, m = map(int, input().split())

ans = [float('inf')]*(n+1)

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

for _ in range(m):

a, b, c = map(int, input().split())

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

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

k = int(input())

friend = [*map(int, input().split())]

for i in range(1, n+1):

dist = dijkstra(i)

ans[i] = sum(dist[f] for f in friend)

print(ans.index(min(ans)))

 

 

문제풀이

• 다익스트라 알고리즘을 활용한다.
• adj에 입력 받은 데이터를 넣어 양방향 간선으로 표시한다.
• 반복문을 이용하여 n개의 방의 다익스트라를 구한다.
  • i번 방에서 각 친구들의 방 위치까지 이동할 때의 최단 거리 합을 구하고, ans[i]에 i번 방까지의 친구들의 이동 거리의 총합을 저장한다.
• 가장 작은 총합 min을 구해 해당 방의 번호 index를 출력한다.