[백준(Baekjoon)][자바(java)] 4386 : 별자리 만들기 / 최소 신장 트리

 

www.acmicpc.net/problem/4386

4386번: 별자리 만들기

 

▶  프림  ( Prim )

import java.io.*;
import java.util.*;

public class Main {
	
	static class Path implements Comparable<Path> {
		int v;
		double w;	// vertex num, weight from adjacnet vertex
		Path( int v, double w ) {
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo( Path o ) {
			return Double.compare( w, o.w );
		}	
	}
	
	static class Node {
		int u, v;
		double w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, double w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
	
	public static double spanning_prim( List<List<Node>> e, int n ) {
		int u, v;  double w_u, w, w_sum = 0;
		boolean c[] = new boolean[n];
		double d[] = new double[n];
		for( int 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;
				w = nd.w;
				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() ), i, j;
		double p[][] = new double[n][2];
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 2; j++ )
				p[i][j] = Double.parseDouble( st.nextToken() );
		}
		br.close();
		
		double w;
		List<List<Node>> e = new LinkedList<>();
		for( i = 0; i < n; i++ )
			e.add( new LinkedList<Node>() );
		for( i = 0; i < n-1; i++ ) {
			for( j = i+1; j < n; j++ ) {
				w = Math.sqrt( Math.pow( p[j][0]-p[i][0], 2 ) + 
				                Math.pow( p[j][1]-p[i][1], 2 ) );
				e.get( i ).add( new Node( i, j, w ) );
				e.get( j ).add( new Node( j, i, w ) );
			}
		}
		
		System.out.printf( "%.2f", spanning_prim( e, n ) );

	}
}

 

▶  크루스칼  ( Kruskal )

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

public class Main {
	
	static class Node implements Comparable<Node> {
		int u, v;
		double w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, double w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo( Node o ) {
			return Double.compare( w, o.w );
		}
	}
	
	public static double spanning_kruskal( PriorityQueue<Node> e, int n ) {
		double w_sum = 0, w; int i, t = 0, u, v;
		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() ), i, j;
		double p[][] = new double[n][2];
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 2; j++ )
				p[i][j] = Double.parseDouble( st.nextToken() );
		}
		br.close();
		
		double w;
		PriorityQueue<Node> e = new PriorityQueue<>();	// edge
		for( i = 0; i < n-1; i++ ) {
			for( j = i+1; j < n; j++ ) {
				w = Math.sqrt( Math.pow( p[j][0]-p[i][0], 2 ) + 
				    Math.pow( p[j][1]-p[i][1], 2 ) );
				e.add( new Node( i, j, w ) );
				e.add( new Node( j, i, w ) );
			}
		}
		
		System.out.printf( "%.2f", spanning_kruskal( e, n ) );

	}
}

 

*  최소 스패닝 트리 ( MST )
-  각 정점의 x, y 좌표를 차례로 입력받음
-  인접한 두 정점 간의 거리가 가중치가 됨
-  최소 가중치의 합을 소수점 둘째 자리까지 출력해야 하므로 printf() 사용