[백준 2887] 행성 터널 (자바)

 

난이도 : 골드 2

 

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

크루스칼 알고리즘을 이용하기 위해서는 간선의 정보가 필요합니다. 행성의 최대 개수는 10만 개가 들어옵니다.

행성 간의 모든 간선을 구하려면 대략 100,000^2의 시간 복잡도가 걸립니다. 시간초과를 예상할 수 있는 크기입니다.

굳이 모든 행성 간의 거리를 구할 필요는 없습니다. 현재 행성에서 가까운 행성간의 거리만 구하면 됩니다. 간선의 가중치는 x, y, z의 최소 값입니다. 

즉, 어떤 행성의 최소 가중치의 간선은 x, y, z별로 정렬한 후 앞, 뒤의 값을 비교하여 구할 수 있습니다.

이해가 되지 않는다면 코드를 보며 이해하시길 바랍니다.

---

전역 변수

int n = 행성의 수

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

Planet planet[] = 행성의 정보를 저장하는 배열

함수

void main

입력을 받고 유니온 파인드를 위한 배열인 parent와 행성의 정보를 담은 배열인 planet을 세팅합니다.

ArrayList를 이용해 x, y, z의 오름차순으로 정렬합니다.

그 후 정렬된 ArrayList에서 각 n-1개의 간선을 뽑아내고 우선순위 큐에 넣어줍니다. 이때의 가중치는 대상 행성의 x, y, z의 거리 중 최솟값입니다.

좌표는 -10억~10억입니다. 그래서 한 좌표에서 나올 수 있는 최대 거리는 20억이 됩니다. 그렇기에 정답인 weight는 long타입으로 선언했습니다.

최소 스패닝 트리의 후보가 될 간선들을 모두 뽑아냈으니 크루스칼 알고리즘을 진행합니다.

 

void union

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

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

 

int find

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

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

 

class Planet

행성의 번호, x 좌표, y 좌표, z 좌표를 저장합니다.

 

class Edge

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

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