[백준/C++][(1197번)최소 스패닝 트리]

문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

이 문제는 최소 스패닝 트리 알고리즘을 사용하면 바로 풀리는 문제이다.

문제해결

1.vector <pair<int,pair<int,int>>> v 를 사용하여 가중치,노드1,노드2 순으로 입력받는다.

2.가중치에 대하여 오름차순으로 정렬한다.

3.parent배열을 모두 parent[i] = i로 초기화 한다 (처음에는 모두 부모가 자기 자신이다 -> 모두 다 끊어진 상태로 시작한다,최소스패닝 알고리즘이다)

4.만약 두 노드가 연결되지 않은 노드라면 연결하고 가중치를 result에 더해간다. ->두 노드가 연결된 유무는 find함수를 통해 알아낸다.

5.그리고 Union함수로 두 함수를 연결해준다.

6. 4,5번 방법을 반복한다.

 

코드

ide.goorm.io/shared_files/sksj0111_a4ee03f393e4a502b8b6b01d29019b561605796608074