[BOJ] 백준 2887번 : 행성 터널 (JAVA)

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

 

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

 

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

 

 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

 

풀이

크루스칼 알고리즘으로 풀 수 있는 문제였습니다.

 

이 문제의 핵심은 3차원 좌표로 이루어진 행성끼리의 비용을 어떻게 구하는지였습니다.

저는 처음에 단순히 2중 반복문을 돌려서 모든 행성 간의 비용을 구했지만, 메모리 초과가 발생하였습니다.

 

그래서 모든 행성의 (x, y, z) 한번에 보지 말고, x, y, z 좌표를 각각 오름차순 정렬해서 그 좌표만을 가지고 행성 간의 비용을 구하기로 하였습니다.

 

예를 들어, x 좌표를 정렬한 값이 0, 3, 8, 10, 15라면, (0, 3), (3, 8), (8, 10), (10, 15)에 대해서 비용을 구하고, edgeList에 추가하면 됩니다.

마찬가지로 y, z 좌표에 대해서 정렬한 값에 대하여 인접한 행성 간의 비용을 구해서 edgeList에 추가합니다.

그리고 edgeList를 비용에 대해서 오름차순으로 정렬한 후, 크루스칼 알고리즘을 수행하시면 됩니다.

 

이렇게 각각의 좌표에 대해 따로 따로 생각해도 되는 이유는 간단합니다.

위에서 예시로 든 x 좌표를 살펴보면, 0 - 3 - 8 - 10 - 15로 연결되어 최소 신장 트리를 만족하는 것은 자명합니다.

마찬가지로, y와 z에 대해서도 최소 신장 트리를 만족하기때문에 각각의 좌표에 대해서 정렬하고 edgeLIst에 추가해도 무방합니다.

 

여기서 또 의문점이 들 수 있는데, 같은 행성끼리의 간선이 중복해서 들어갈 수 있습니다.

하지만, x, y, z 중 가장 작은 비용만 채택되기때문에 행성의 연결 조건( min(|xA-xB|, |yA-yB|, |zA-zB|) ) 에 부합합니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

 

참고

코드 중간에 '->'가 들어간 부분을 처음 보시는 분이 있을까봐 참고 링크를 올립니다.

위의 방식은 람다표현식이며, 아래 포스팅을 읽어보시길 바랍니다.

 

 

Comparator와 Comparable의 차이 + 람다표현식

 

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.