[백준(Baekjoon)][자바(java)] 2887 : 행성 터널 / 최소 신장 트리

 

www.acmicpc.net/problem/2887

2887번: 행성 터널

 

▶  프림  ( Prim )   -->  시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static class Point {
		int i, x, y, z;
		Point( int i, int x, int y, int z ) {
			this.i = i;
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
	
	static class Path implements Comparable<Path> {
		int v, w;	// vertex num, weight from adjacnet vertex
		Path( int v, int w ) {
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo( Path o ) {
			return w - o.w;
		}	
	}
	
	static class Node {
		int u, v, w;
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
	
	public static int spanning_prim( List<List<Node>> e, int n ) {
		int u, v, i, w_u, w, w_sum = 0;
		boolean c[] = new boolean[n];
		int d[] = new int[n];
		for( i = 1; i < n; i++ )
			d[i] = Integer.MAX_VALUE;
		PriorityQueue<Path> pq = new PriorityQueue<>();
		pq.add( new Path( 0, 0 ) );
		while( !pq.isEmpty() ) {
			Path p = pq.remove();
			u = p.v; w_u = p.w;
            if( d[u] < w_u ) continue;
			if( c[u] ) continue;
			c[u] = true;
			w_sum += w_u;
			for( Node nd : e.get(u) ) {
				v = nd.v;	// connectnd vertex num
				w = nd.w;	// connectnd weight
				if( d[v] > w && !c[v] ) {
					pq.add( new Path( v, w ) );
					d[v] = w;
				}
			}
		}
		return w_sum;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		int n = Integer.parseInt( br.readLine() ), x, y, z, i, j;
		Point p[] = new Point[n];
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			x = Integer.parseInt( st.nextToken() );
			y = Integer.parseInt( st.nextToken() );
			z = Integer.parseInt( st.nextToken() );
			p[i] = new Point( i, x, y, z );
		}
		br.close();
		
		List<List<Node>> e = new LinkedList<>();
		for( i = 0; i < n; i++ )
			e.add( new LinkedList<Node>() );
		
		Arrays.sort( p, ( o1, o2 ) -> o1.x - o2.x );
		for( i = 0; i < n-1; i++ ) {
			j = i+1;
			e.get( p[i].i ).add( new Node( p[i].i, p[j].i, Math.abs( p[i].x - p[j].x ) ) );
		}
		Arrays.sort( p, ( o1, o2 ) -> o1.y - o2.y );
		for( i = 0; i < n-1; i++ ) {
			j = i+1;
			e.get( p[i].i ).add( new Node( p[i].i, p[j].i, Math.abs( p[i].y - p[j].y ) ) );
		}
		Arrays.sort( p, ( o1, o2 ) -> o1.z - o2.z );
		for( i = 0; i < n-1; i++ ) {
			j = i+1;
			e.get( p[i].i ).add( new Node( p[i].i, p[j].i, Math.abs( p[i].z - p[j].z ) ) );
		}
		
		for( i = 0; i < n; i++ )
			Collections.sort( e.get(i) );

		System.out.println( spanning_prim( e, n ) );

	}
}

 

▶  크루스칼  ( Kruskal )

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

public class Main {
	
	static class Point {
		int i, x, y, z;
		Point( int i, int x, int y, int z ) {
			this.i = i;
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
	
	static class Node implements Comparable<Node> {
		int u, v, w;
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo( Node o ) {
			return this.w - o.w;
		}
	}
	
	public static int spanning_kruskal( PriorityQueue<Node> e, int n ) {
		int w_sum = 0, i, t = 0, u, v, w;
		int p[] = new int[n];  // make set
		int r[] = new int[n];  // rank
		for( i = 0; i < n; i++ )
			p[i] = i;
		while( t < n-1 && !e.isEmpty() ) {
			Node nd = e.remove();
			u = nd.u; v = nd.v; w = nd.w;
			if( find( u, p ) != find( v, p ) ) {  // find set
				w_sum += w;
				union( u, v, p, r );  // union set
				t++;
			}
		}
		return w_sum;
	}
	public static int find( int n, int p[] ) {
		if( n == p[n] ) 
			return n;
		return p[n] = find( p[n], p );
	}
	public static void union( int a, int b, int p[], int r[] ) {
		a = find( a, p );
		b = find( b, p );
		if( r[a] > r[b] )
			p[b] = a;
		else {
			p[a] = b; 
			if( r[a] == r[b] )
				r[b]++;
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		int n = Integer.parseInt( br.readLine() ), x, y, z, i, j;
		Point p[] = new Point[n];
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			x = Integer.parseInt( st.nextToken() );
			y = Integer.parseInt( st.nextToken() );
			z = Integer.parseInt( st.nextToken() );
			p[i] = new Point( i, x, y, z );
		}
		br.close();
		
		PriorityQueue<Node> e = new PriorityQueue<>();
		Arrays.sort( p, ( o1, o2 ) -> o1.x - o2.x );
		for( i = 0; i < n-1; i++ ) {
			j = i+1;
			e.add( new Node( p[i].i, p[j].i, Math.abs( p[i].x - p[j].x ) ) );
		}
		Arrays.sort( p, ( o1, o2 ) -> o1.y - o2.y );
		for( i = 0; i < n-1; i++ ) {
			j = i+1;
			e.add( new Node( p[i].i, p[j].i, Math.abs( p[i].y - p[j].y ) ) );
		}
		Arrays.sort( p, ( o1, o2 ) -> o1.z - o2.z );
		for( i = 0; i < n-1; i++ ) {
			j = i+1;
			e.add( new Node( p[i].i, p[j].i, Math.abs( p[i].z - p[j].z ) ) );
		}

		System.out.println( spanning_kruskal( e, n ) );

	}
}

 

*  최소 스패닝 트리 ( MST )

-  인덱스, x 좌표, y 좌표, x 좌표의 속성을 가진 Point 클래스 생성
-  Point[] 배열에 점들을 입력받음
-  x 좌표를 기준으로 Point[] 배열을 오름차순으로 정렬 후 인접한 정점 간의 거리를 e( edge )에 추가
-  y 좌표를 기준으로 Point[] 배열을 오름차순으로 정렬 후 인접한 정점 간의 거리를 e( edge )에 추가
-  z 좌표를 기준으로 Point[] 배열을 오름차순으로 정렬 후 인접한 정점 간의 거리를 e( edge )에 추가
-  크루스칼 알고리즘으로 가중치가 작은 간선부터 선택( 우선순위 큐 이용 )하며 최소 스패닝 트리 생성