개발자 퉁이리

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 최소 스패닝 트리 ⊙ 문제 접근 과정 문제를 보면 최소 스패닝 트리, MST 문제이다. 유지비를 최소로 길을 전부 터야 한다. 길을 입력받고 오름차순으로 정렬한다. 오름차순 정렬 후, 최소 스패닝 트리를 돌려준다. 부모가 다르면 값을 비교 후 작은 값이면 연결시켜 갱신, 같으면 패스한다...

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 정렬 최소 스패닝 트리 ⊙ 문제 접근 과정 먼저 사용자에게 입력받은 3차원 행성 좌표를 저장한다. 그리고 그 값들을 토대로 행성 사이의 거리를 각각 구해주고 크루스칼 알고리즘을 사용한다. 크루스칼 알고리즘을 사용하면 최소 스패닝 트리를 구할 수 있다. 최소 스패닝 트리란 신장 트리 중에서도 최..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 최소 스패닝 트리 ⊙ 문제 접근 과정 이번에 다뤄볼 문제는 MST 알고리즘이다. MST는 최소 스패닝 트리로 스패닝 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다. MST의 구현 방법에는 Kruskal MST 알고리즘과 Prim MST 알고리즘이 있는데 이번 문제..