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

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

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방의 개수 N (2 ≤ N ≤ 100), 비밀통로의 개수 M(N-1 ≤ M ≤ N(N - 1)/2)이 공백으로 구분되어 주어진다. 그 다음 줄부터 M개의 줄에 걸쳐 비밀통로의 정보(a, b, c)가 주어진다. a와 b는 비밀통로로 연결된 두 방의 번호이며 c는 a와 b를 연결하는 비밀통로의 길이이다. a와 b는 항상 다르며 c는 1 이상 1,000 이하의 자연수이다. 두 방을 연결하는 비밀통로는 반드시 하나씩만 존재한다. 또한 어떤 방에서 다른 방으로 비밀통로를 이용해서 갈 수 없는 경우는 존재하지 않으며, 같은 비밀통로에 대한 정보가 중복되어 주어지지 않는다. 비밀통로의 정보가 모두 주어진 다음 그 다음 줄에 모임에 참여하는 친구의 수 K(1 ≤ K ≤ N)가 주어진다. 각 테스트 케이스의 마지막 줄에는 모임에 참여하는 친구들이 현재 위치해 있는 방의 번호 K개가 공백으로 구분되어 주어진다. 친구들이 있는 방은 항상 N개의 방 중 하나이며, 방 번호가 중복되는 경우는 없다. 즉, 두 명 이상이 한 방에 있는 경우는 입력으로 주어지지 않는다. 

 

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 각 테스트 케이스의 답을 순서대로 1줄에 1개씩 출력한다. 각 테스트 케이스마다 모임에 참여하는 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소의 방 번호를 출력한다. 만약 그러한 장소가 여러 개일 경우, 그중 번호가 가장 작은 방의 번호를 출력한다.

문제 코드

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

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

T = int(input())

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())
    students = list(map(int, input().split()))
    
    total_distances = [0] * (N + 1)
    for student in students:
        distances = dijkstra(student, N, graph)
        for i in range(1, N + 1):
            total_distances[i] += distances[i]
    
    min_dist = INF
    answer = 1
    for room in range(1, N + 1):
        if total_distances[room] < min_dist:
            min_dist = total_distances[room]
            answer = room
            
    print(answer)

 

문제 해설

 

1. 각 학생들의 위치에서 모든 방까지의 최단 거리를 다익스트라 알고리즘으로 계산

2. 각 방마다 모든 학생들의 이동거리 합계(total_distance)를 구함

3-1. total_distance가 최소가 되는 방 번호를 찾아 출력

3-2. 여러 개인 경우 가장 작은 방 번호 선택