백준 1922번 네트워크 연결

< 백준 1922번 네트워크 연결 - 마포 코딩박 >

사용한 알고리즘: MST


두 개의 컴퓨터를 연결하는데 비용이 들 때 모든 컴퓨터를 연결하는데 필요한 최소 비용을 구하는 문제였습니다. MST의 대표적인 문제였습니다.
 (보통 MST 구현에 struct로 저장하고 이를 pq로 돌리지만, 연결 비용의 최대값이 10^4으로 작게 주어져 배열을 사용했습니다.)

문제풀이는 다음과 같습니다.

(1) (코드 13~23)
 MST 구현을 하려면 Union-Find 가 필요합니다.
 두 컴퓨터 a, b가 연결되었는지(같은그룹인지) 판단하고 연결을 해주는 역할을 합니다.

(2) (코드 10~13, 35~50)
 'cost[x] : x 비용으로 연결가능한 컴퓨터 a, b 저장' 이라고 설정하고 비용을 작은것부터 (1->10^4) 순서대로 돌아보며 Union-Find 를 써서 연결해야하는지 여부를 판단했습니다.
 N 개의 컴퓨터를 한 그룹으로 연결하려면 N-1번의 연결이 필요합니다.