백준 2887 - 행성 터널

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

2887번: 행성 터널

 

문제 설명

때는 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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

 

문제 풀이

특정 좌표를 기준으로 정렬을 하면 위에서부터 아래로 인접한 행성이 가장 가까운 행성이 될 것이라고 생각했다.

그래서 x,y,z를 기준으로 정렬을 3번 진행한 후에, 터널 건설의 비용을 모두 List에 넣고 Prim 알고리즘을 활용해 최저 비용을 구했다.

2번째 요소를 넣을 때 for문을 1부터 시작해서 계속 틀렸다. 인덱스 관리 잘하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Node implements Comparable<Node>{
		long Node,weight;

		public Node(long Node, long weight) {
			super();
			this.Node = Node;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return (int) (this.weight-o.weight);
		}
	}
	static long[][] map;
	static boolean[] visited;
	
	static int N;
	static long answer;
	static List<Node>[] list;
	static PriorityQueue<Node> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new long[N][4];
		list = new List[N+1];
		visited = new boolean[N+1];
		for(int i=0; i<N+1;i++) {
			list[i] = new ArrayList<>();
		}
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
			map[i][3] = i+1;
		}
        //0번째 요소로 정렬(x)
		Arrays.sort(map, (o1, o2) -> {
            return Long.compare(o1[0], o2[0]);
        });
		//0번째 요소로 정렬된 값 insert
		for(int i=0; i<N-1; i++) {
			list[(int) map[i][3]].add(new Node(map[i+1][3],Math.abs(map[i][0]-map[i+1][0])));
			list[(int) map[i+1][3]].add(new Node(map[i][3], Math.abs(map[i][0]-map[i+1][0])));
		}
		
		//1번째 요소로 정렬(y)
		Arrays.sort(map, (o1, o2) -> {
            return Long.compare(o1[1], o2[1]);
        });
		//1번째 요소로 정렬된 값 insert
		for(int i=0; i<N-1; i++) {
			list[(int) map[i][3]].add(new Node(map[i+1][3],Math.abs(map[i][1]-map[i+1][1])));
			list[(int) map[i+1][3]].add(new Node(map[i][3], Math.abs(map[i][1]-map[i+1][1])));
		}
        //2번째 요소로 정렬(z)
		Arrays.sort(map, (o1, o2) -> {
            return Long.compare(o1[2], o2[2]);
        });
		//2번째 요소로 정렬된 값 insert
		for(int i=0; i<N-1; i++) {
			list[(int) map[i][3]].add(new Node(map[i+1][3],Math.abs(map[i][2]-map[i+1][2])));
			list[(int) map[i+1][3]].add(new Node(map[i][3], Math.abs(map[i][2]-map[i+1][2])));
		}
		
		//prim 진행
		pq.add(new Node(1,0));
		while(!pq.isEmpty()) {
			Node temp = pq.poll();
			if(visited[(int) temp.Node]) continue;
			int to = (int) temp.Node;
			long weight = temp.weight;
			visited[to] = true;
			answer+=weight;
			for(Node next : list[to]) {
				if(!visited[(int) next.Node]) {
					pq.add(next);
				}
			}
		}
		System.out.println(answer);
	}
}