Arctic Network

• 문제 설명이 좀 헷갈린다.
• 위성은 경로에 설치하는 것이 아니라, 노드에 설치하는 것이고, 위성이 설치된 노드끼리 통신이 가능하게 되는 것이다.
• 결국. S개의 위성이 있다는 것은 S개의 컴포넌트를 연결해줄수 있다는 말이다.
• 따라서 풀이는, 최소 신장 트리 (Minimum Spanning Tree / MST)를 만든 뒤에 가장 코스트가 비싼 엣지 S-1개를 지우고, 이렇게 생긴 S개의 컴포넌트를 위성으로 연결해 주는 것이다. 도시 분할 계획과 동일한 아이디어인데, 컴포넌트가 2개가 아니라 S개라는 것만 다르다. 답은 MST를 이루는 엣지들 중에서 S번째로 코스트가 비싼 엣지의 코스트가 된다. MST를 만든 다음 엣지를 제거하는 대신, 크루스칼 알고리즘을 변형해서 S개의 컴포넌트가 남을때까지 엣지를 추가해줘도 된다.
• 사실 노드가 평면상의 좌표들이기 때문에, MST를 구하기 위해서 유클리디안 최소 신장 트리 (Minimum Spanning Tree / MST) 알고리즘을 사용할수 있다. 거기까지는 안쓰더라도, O(V^2) 프림 알고리즘을 사용하면 그냥 크루스칼 알고리즘을 쓰는것 보다 조금 더 빠르다

"""Solution code for "BOJ 4343. Arctic Network".

- Problem link: https://www.acmicpc.net/problem/4343
- Solution link: http://www.teferi.net/ps/problems/boj/4343

Tags: [Minimum spanning tree]
"""

import math
import sys
from teflib import graph as tgraph


def main():
    N = int(sys.stdin.readline())
    for _ in range(N):
        S, P = [int(x) for x in sys.stdin.readline().split()]
        coords = [
            [int(x) for x in sys.stdin.readline().split()] for _ in range(P)
        ]

        mat_graph = tgraph.create_mat_graph(
            P, lambda u, v: math.dist(coords[u], coords[v]))
        mst_edges = tgraph.minimum_spanning_tree_dense(mat_graph)
        answer = mst_edges[-S][2]
        print(f'{answer:.2f}')


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.graph.minimum_spanning_tree_dense
  • teflib.graph.create_mat_graph