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

 

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static class Point {
		int x, y;
		Point( int x, int y ) {
			this.x = x;
			this.y = y;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Point other = (Point) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}
	}
	
	static class Node implements Comparable<Node> {
		int u, v, w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo( Node o ) {
			return 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], r[] = new int[n];
		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( union( u, v, p, r ) ) {  // union set
				w_sum += w;
				t++;
			}
		}
		for( i = 0; i < n-1; i++ )
			if( find( i, p ) != find( i+1, p ) )
				return -1;
		return w_sum == 0 ? -1 : 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 boolean union( int a, int b, int p[], int r[] ) {
		if( a == b ) return false;
		a = find( a, p );
		b = find( b, p );
		if( a == b ) return false;
		if( r[a] > r[b] )
			p[b] = a;
		else {
			p[a] = b; 
			if( r[a] == r[b] )
				r[b]++;
		}
		return true;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), 
		    m = Integer.parseInt( st.nextToken() );
		int map[][] = new int[n][m], t, i, j;  // tmp
		boolean v[][] = new boolean[n][m];  // visited
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < m; j++ ) {
				t = Integer.parseInt( st.nextToken() );
				map[i][j] = t;
				if( t == 0 ) 
					v[i][j] = true;
			}
		}
		br.close();
		
		int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 }, c = 0, x, y, nx, ny, u;  Point p;
		HashMap<Integer,List<Point>> hm = new HashMap<>();
		Deque<Point> q;
		for( i = 0; i < n; i++ ) {
			for( j = 0; j < m; j++ ) {
				if( map[i][j] == 1 && !v[i][j] ) {
					hm.put( c, new ArrayList<>() );
					q = new LinkedList<>();
					q.add( new Point( i, j ) );
					v[i][j] = true;
					while( !q.isEmpty() ) {
						p = q.poll();
						hm.get( c ).add( p );
						x = p.x;  y = p.y;
						for( u = 0; u < 4; u++ ) {
							nx = x + dx[u];
							ny = y + dy[u];
							if( nx < 0 || nx >= n || ny < 0 || ny >= m )
								continue;
							if( !v[nx][ny] ) {
								q.add( new Point( nx, ny ) );
								v[nx][ny] = true;
							}
						}
					}
					c++;
 				}
			}
		}
		
		final int max = 10;
		int s = hm.size(), d[][] = new int[s][s], a, b;
		for( i = 0; i < s; i++ )
			for( j = 0; j < s; j++ )
				d[i][j] = max;
		List<Point> ls, lls;  int l, ddx, ddy, nnx, nny;
		for( int k : hm.keySet() ) {
			ls = hm.get( k );
			a = k;
			for( Point pp : ls ) {
				x = pp.x; y = pp.y;
				loop:
				for( u = 0; u < 4; u++ ) {
					nx = x + dx[u];
					ny = y + dy[u];
					if( nx < 0 || nx >= n || ny < 0 || ny >= m )
						continue;
					if( map[nx][ny] == 1 )
						continue;
					ddx = dx[u];
					ddy = dy[u];
					q = new LinkedList<>();
					q.add( new Point( nx, ny ) );
					l = 0;
					while( !q.isEmpty() ) {
						l++;
						p = q.poll();
						nnx = p.x + ddx; nny = p.y + ddy;
						if( nnx < 0 || nnx >= n || nny < 0 || nny >= m )
							continue;
						if( map[nnx][nny] == 1 ) {
							for( int kk : hm.keySet() ) {
								if( l == 1 )
									continue loop;
								lls = hm.get(kk);
								if( lls.contains( new Point( nnx, nny ) ) ) {
									b = kk;
									d[a][b] = Math.min( d[a][b], l );
									d[b][a] = d[a][b];
									continue loop;
								}
							}
						}
						q.add( new Point( nnx, nny ) );
					}
				}
			}
		}
		
		PriorityQueue<Node> e = new PriorityQueue<>(); // edge
		for( i = 0; i < s; i++ )
			for( j = i+1; j < s; j++ )
				if( d[i][j] != max )
					e.add( new Node( i, j, d[i][j] ) );
		
		System.out.println( spanning_kruskal( e, s ) );
			
	}
}

 

*  BFS, Hash, 유니온 파인드, 최소 신장 트리

-  map의 크기와 정보를 입력받은 후, map의 정보가 1일 경우( 섬일 경우 )에만 BFS하여 섬의 개수와 범위를 구함
   각 섬에 번호를 부여하여 HashMap에 넣음
 ( key : 섬의 번호, value : 그 섬에 해당하는 Point들의 리스트 )
-  섬의 번호가 정점 번호, 두 섬 사이의 거리가 가중치라고 가정하고 거리의 최솟값을 담은 배열 d[][] 생성
 ( 최댓값으로 초기화 )  ( ex) 섬1, 2 사이의 최소 거리가 3일 때 d[1][2] = 3 )
-  해시맵을 순차적으로 탐색하며 각 Key( 섬 번호 )의 각 Point들 중에서 상하좌우 중에 값이 0인 Point를 찾아서
   다른 섬( map정보가 1인 )을 발견할 때까지 Queue에 넣어가며 탐색하고, 그 Point가 어떤 섬에 속한건지
   번호를 구해 Node 객체를 생성하여 간선 PriorityQueue에 넣는다 ( Node - u, v, w )
-  만들어진 간선들로 크루스칼 알고리즘을 돌려 최소 비용을 구함
 ( 사이클 있을 경우 간선 추가 안 함 -- 유니온 파인드 )
 ( 모든 정점들이 연결되지 않은 경우 -1 -- 각 정점을 find()함수로 root 정점을 구하고 그 다음 정점의 루트와 같은지 비교 )
 ( 비용의 합이 0일 경우 -1 )