o_onn5

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소스패닝 트리를 만드는 크루스칼 문제다. 전형적인 크루스칼 문제라서 개념을 아는 사람이라면 쉽게 풀 수 있다. import math # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) ret..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 크루스칼 문제다. 일반적인 크루스칼 개념을 적용시켜서 푸는 것은 동일하다. 각 노드의 x축 y축 z축 차이를 탐색한 뒤에 절댓값이 가장 작은 가중치를 선택하면 된다. 그렇다고 모든 노드를 하나씩 비교해보면 시간초과가 난다. 따라서 간선의 가중치와 노드를 저장한 뒤에 우선순위 정렬을 시행한 뒤 비교해줘야한다. 정리해보면 1. x축 y축 z축의 리스트를 하나 만든다. ..

최소신장트리(MST, MinimumSpanningTree)를 구하는 알고리즘 중 하나이다. 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없어야하고 간선의 가중치가 최소가 되는 트리를 의미한다. 아래의 그림이 바로 그런 예시다. 알고리즘은 대략적으로 다음과 같다. 1. 가장 작은 가중치의 간선 탐색 2. 사이클이 생기지 않는 노드인지 확인 3-1. 사이클이 생긴다면 pass 3-2. 사이클이 생기지 않으면 해당 간선 리스트에 저장 아래 코드는 MST의 최소 가중치를 구하는 코드다. # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_..