while (1): study();

출처: https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 무향그래프에 대해서 최소 신장트리를 구하는 문제이므로, 크루스칼 알고리즘을 적용하면 쉽게 풀 수 있습니다. 크루스칼 알고리즘: https://jcy1996.tistory.com/35 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘에 대해 이해하기 위해서는 먼저 신장 트리(Spanning Tree)에 대해 이해할 필요가 있습니다. 신장 트..

문제 한 마을은 N개의 집과 M개듸 도로로 구성되어 있습니다. 각 집은 0번부터 N - 1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작..

크루스칼 알고리즘에 대해 이해하기 위해서는 먼저 신장 트리(Spanning Tree)에 대해 이해할 필요가 있습니다. 신장 트리(Spanning Tree) 신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하는 부분 그래프를 의미합니다. 위의 그림이 직관적으로 신장 트리를 이해하는 데 도움이 되는 것 같습니다. 실제 그래프 관계는 훨씬 복잡하지만, 굵은 실선만 이어도 모든 노드에 대해서 연결할 수 있다는 것이 특징입니다. 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 가능한 최소 비용의 신장 트리를 찾아주는 알고리즘입니다. 다음과 같은 순서로 처리됩니다. 1. 모든 간선에 대해 비용순으로 정렬을 수행합니다. 2. 거리가 짧은 간선부터 집합에 포함시킵니다. 3. 단, 사이클이 ..