[백준(Baekjoon)][자바(java)] 4195 : 친구 네트워크 / 유니온 파인드

 

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

문제 풀이

 

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

public class Main {
	
	public static int find( int n, int p[] ) {
		if( n == p[n] ) 
			return n;
		return p[n] = find( p[n], p );
	}
	public static int union( int a, int b, int p[], int s[] ) {
    	if( a == b ) return s[a];
		a = find( a, p );
		b = find( b, p );
		if( a == b ) return s[a];
		p[b] = a; 
		return s[a] += s[b];
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int t = Integer.parseInt( br.readLine() ), n, p[], s[], c, a, b, i, j;
		String f[][];
		StringTokenizer st; 
		HashMap<String, Integer> hm;
		StringBuilder sb = new StringBuilder();
		while( t-- > 0 ) {
			n = Integer.parseInt( br.readLine() );
			hm = new HashMap<>();
			f = new String[n][2];
			c = 0;
			for( i = 0; i < n; i++ ) {
				st = new StringTokenizer( br.readLine() );
				for( j = 0; j < 2; j++ ) {
					f[i][j] = st.nextToken();
					if( !hm.containsKey( f[i][j] ) )
						hm.put( f[i][j], c++ );
				}
			}
			p = new int[c];
			s = new int[c];
			for( i = 0; i < c; i++ ) {
				p[i] = i;
				s[i]++;
			}
			for( i = 0; i < n; i++ ) {
				a = hm.get( f[i][0] );
				b = hm.get( f[i][1] );
				sb.append( union( a, b, p, s ) + "\n" );
			}
		}
		br.close();
		System.out.println( sb.toString() );
		
	}
}

 

*  유니온 파인드

-  각 집합의 부모 집합의 인덱스를 저장하는 p[] 배열 외에 각 집합의 사이즈를 저장하는 s[] 배열을 추가로 생성
-  각 집합의 초기 크기는 1 ( 하나의 정점 )
-  Union 함수를 집합의 크기를 리턴하도록 수정  ( return s[i] )
-  각 정점의 입력값( 친구의 이름 )이 String 이고, 고유하므로 HashMap에 친구의 이름을 key로 하고 인덱스를 부여하여 value로 넣음
-  연산 시 hashMap에서 value 사용

 

( hyunjiishailey.tistory.com/283 )