[백준_BOJ] 1922. 네트워크 연결 _ JAVA

문제

 

 

 

 

 

 

 

 

풀이

 

 

크루스칼 알고리즘을 이용해서 풀이한 문제입니다.

크루스칼 알고리즘을 이용하기 위해 3가지 메서드 union, find, isSame을 만들어주었습니다.

 

추가적으로 비용이 적은 간선들부터 연결해주기 위해 Priority Queue를 사용했습니다.

Comparable을 이용해 비용순으로 정렬해서 이용하였습니다.

 

먼저, union 메서드에서는 시작점과 도착점 x, y를 매개변수로 입력받아서

find(x) 와 find(x)가 같지 않다면, 서로 다른 그룹에 속해 있는 것이므로

두 그룹 중에서 작은 값으로 합쳐주었습니다.

크기를 비교하여 합쳐주지 않고 그냥 x나 y로 합쳐주어도 괜찮지만

작은 번호로 합쳐주면 검색 속도를 높여줄 수 있습니다.

 

find 메서드는 자신이 그룹 번호와 같은 경우, 자기 자신을 반환해주었고

자기 자신이 그룹 번호와 같지 않다면, find(parent(x))를 이용하여 그룹에서 

부모 (대표 번호) 가 되는 값을 찾아 반환시켜 주었습니다.

 

마지막으로 union 메서드는 서로 다른 그룹에 속해 있는지를 확인합니다.

이는 이미 같은 그룹에서는 추가적으로 연결해주면 최소값을 제대로 찾지 못하기 때문입니다.

 

 

크루스칼과 union-find에 대해 알고 있으시다면 충분히 풀이할 수 있는 문제인 것 같습니다.

 

 

 

 

코드

 

 

 

 

 

 

 

 

출처

 

 

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

1922번: 네트워크 연결