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 풀이 최소 신장 트리는 크루스칼 알고리즘과 프림 알고리즘으로 해결할 수 있다. 나는 그 중 크루스칼 알고리즘을 풀었다. Edge 클래스를 만들어 각 간선의 정점, 가중치 값을 담고 가중치 오름차순으로 정렬했다. 가중치가 작은 것부터 시작해서 간선이 잇는 두 정점이 같은 그룹이 아니라면 선택하는 방식이다. 두 정점이 이미 같은 그룹이라면 다시 선택했을 ..

https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용해 최소 신장 트리를 구하되, 간선을 선택할 때 여초와 여초, 남초와 남초가 이어진 경우는 제외한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import..