[백준 1197] 최소 스패닝 트리 (자바)

난이도 : 골드 4

 

크루스칼 알고리즘을 이용하여 풀었습니다.

크루스칼 알고리즘은 모든 간선을 오름차순으로 정렬하여 가장 작은 값부터 골라 MST(Minimum Spanning Tree)를 구성합니다. 단, 이때 사이클이 생기는 간선은 추가할 수 없습니다.

간선을 오름차순 정렬하여 하나씩 뽑는 것은 우선순위 큐, 사이클 검사는 Union-Find를 이용했습니다.

2020/11/06 - [정보/CS] - Union-Find 유니온 파인드

Union-Find 유니온 파인드

유니온 파인드 설명입니다.

 

이제 크루스칼 알고리즘의 동작을 살펴보겠습니다.(parent 표의 7은 오류입니다.)

초기 그래프 모양과 유니온 파인드용 parent 배열, 간선을 (v1, v2, weight)로 표현했고 간선은 weight순으로 정렬된 상태입니다.

가장 최소 가중치의 간선인 (1, 2, 1)를 MST에 추가했습니다. parent에도 변화가 있습니다.

간선을 순서대로 추가한 모습입니다. 다음은 (1, 4, 3)인데 find(1) == find(4) 입니다.

즉, 이 간선을 추가하면 사이클이 형성된다는 의미입니다. 이 간선은 크루스칼의 조건에 맞지 않으니 추가할 수 없습니다.

최종적으로 만들어진 MST입니다.(parent 표에 7은 오류라서 삭제했습니다.)

parent[5] == 4인데 Union-Find를 제 포스트를 통해 공부하셨다면 find(5) == 1이란 것을 알 수 있습니다.

---

전역 변수

int parent[] = 그룹의 대표를 나타내는 배열

함수

void main

입력을 받고 유니온 파인드를 위한 배열인 parent를 세팅합니다.

그리고 크루스칼 알고리즘을 실행합니다.

(union 호출)

 

void union

두 개의 파라미터를 서로 연결합니다. 각 도시의 그룹 대표를 p1, p2로 구합니다.

그리고 그룹의 가장 작은 값이 그룹 대표가 되므로 작은 값을 기준으로 넣어줍니다.

 

int find

입력받은 수의 대푯값을 반환합니다.

재귀를 통해 구현했으며 재귀 과정에서 최적화를 거칩니다. 종료 시점은 파라미터의 대표가 곧 자신일 때(그룹의 가장 작은 수)입니다.

 

class Edge

간선의 정보를 저장합니다. 연결된 행성 v1, v2와 가중치 weight를 가집니다.

우선순위 큐의 타입이 될 것이므로 Comparable을 implements 해줍니다.