[백준(Baekjoon)][자바(java)] 1717 : 집합의 표현 / 유니온 파인드

 

www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

문제 풀이

 

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

public class Main {
	
	public static int find( int x, int p[] ) {
		if( x == p[x] ) 
			return x;
		return p[x] = find( p[x], p );
	}
	public static void union( int a, int b, int p[] ) {
        if( a == b )  return;
		a = find( a, p );
		b = find( b, p );
        if( a == b )  return;
		p[b] = a;
	}
    /*
    public static void union2( int a, int b, int p[] ) {
		if( a == b )  return;
		a = find( a, p );
		b = find( b, p );
		if( a == b )  return;
		if( a > b )
			p[a] = b;
		else
			p[b] = a;   
	}
    public static void union3( int a, int b, int p[], int r[] ) { 
		if( a == b )  return;
		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 = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), 
		    m = Integer.parseInt( st.nextToken() ), c, a, b, i;
		int p[] = new int[n+1]; //, r[] = new int[n+1];
		for( i = 0; i <= n; i++ )
			p[i] = i;
		StringBuilder sb = new StringBuilder();
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			c = Integer.parseInt( st.nextToken() );	// command
			a = Integer.parseInt( st.nextToken() );
			b = Integer.parseInt( st.nextToken() );
			if( c == 0 )
				union( a, b, p );
                //union2( a, b, p );
                //union3( a, b, p, r );
			else if( c == 1 )
				sb.append( ( find( a, p ) == find( b, p ) ? "YES" : "NO" ) + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );

	}
}

 

*  유니온 파인드 ( Union-Find )

-  두 집합을 합치는 union(), 해당 원소를 가진 집합을 찾아내는 find() 함수 생성
-  각 집합이 속하는 루트 집합의 인덱스를 저장하는 p[] 배열 생성
-  입력받은 값들에서 첫번째 숫자( 명령어 )가 0이면 union 연산 수행, 1이면 각 노드에 대해 find 연산을 수행 하여 두 집합이 같은 집합에 속해있는지 판단

 

※  유니온 파인드 ( Union-Find )

-  상호 배타적인 집합( Disjoint Set )을 표현할 때 쓰는 자료구조
-  연산의 종류
  ┌ Make-Set(x) : 원소 x로만 구성된 집합을 만든다
  ├ Find-Set(x) : 원소 x를 가진 집합을 알아낸다
  └ Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합침