[백준/C++][(1922번) 네트워크 연결]

문제

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

1922번: 네트워크 연결

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

문제해결

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_c398eda5b476b47e3b4a2001c3f201db1605796564127

1922.cpp - goorm