겜돌이의 개발일지

문제 백준 1647 도시 분할 계획 C++ 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 스패닝 트리를 이용한다. 1. 엣지들을 가중치에 대해 오름차순으로 정렬해주고 2. 최소 스패닝 트리를 만족하도록 가중치가 낮은 n - 2개의 엣지를 연결하면 두 그룹으로 나뉘게 된다. 3. 지금까지의 가중치의 합(ans)가 정답이 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

문제 백준 1197 최소 스패닝 트리 C++ 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용합니다. 1. 간선들을 가중치 기준 오름차순으로 정렬합니다. 2. 간선의 시작과 끝이 연결되지 않았다면 (부모가 같지 않다면) 연결하고 가중치를 더해줍니다. 2-1. 시작과 끝이 연결된 경우에는 해당 간선은 연결할 필요가 없으므로 무시합니다. 3. 간선 배열을 모두 확인해 준 뒤 답을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10..