[백준 1197] 최소 스패닝 트리

글에 개요

백준 알고리즘 1197번 "최소 스패닝 트리" 문제입니다. 최소 스패닝 트리 문제 즉 크루스칼 알고리즘을 알면 쉽게 해결할 수 있습니다.

앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.

크루스칼 알고리즘 (Kruskal Algorithm)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!

또한 참고할 글 2번은 크루스칼 알고리즘에는 Union-Find 알고리즘이 필요하므로 안 읽어 보시면 좋습니다.

이 후 이 문제를 통해 확장할 수 있는 알고리즘이 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 1197] 최소 스패닝 트리: https://www.acmicpc.net/problem/1197

참고할 글

1. http://brenden.tistory.com/36 ([알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) 정리글)
2. http://brenden.tistory.com/33 ([알고리즘] 유니온 파인드(Union-Find) 정리글)

핵심 내용

1. Union-Find 알고리즘을 사용한다.
2. Edge 객체를 생성해줍니다.
3. Edge를 가중치를 기준으로 오름차순으로 나열해줍니다.
4. 사이클 테이블을 확인하여 노드를 연결해주는 작업을 반복합니다.

해결 방법

1. 간성정보를 담는 리스트를 만들어 데이터를 담아줍니다.
2. Collections.sort(edgeList)를 통해 가중치를 기준으로 오름차순으로 나열해줍니다.
3. 사이클 테이블을 확인하여 노드가 연결되지 않았다면 union을 해주고 가중치를 sum 변수에 더해줍니다.

해결한 코드

백준 참고 내용

최소 스패닝 트리 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	8726	3558	1951	37.686%

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않는다.

최소 스패닝 트리의 가중치가 -2147483648보다 크거나 같고, 2147483647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 1 

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1 

3