[백준] 1717 집합의 표현 - 유니온파인드(Union Find) JAVA

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

코드설명

유니온 파인드 문제입니다.

 

배열을 활용한 유니온파인드의 기본구조를 활용하여 풀어보았습니다.

 

유니온 파인드의 핵심코드 구현부분입니다.

public static int findParent(int x) {
    if(x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}
 
public static void unionFind(int a, int b) {
    a = findParent(a);
    b = findParent(b);
 
    if( a < b) {
        parent[b] = a;
    }else if(a >= b) {
        parent[a] = b;
    }
}

이 부분에서 findParent 부분의 구현 부분에서 처음에 헷갈렸던 부분은,

재귀형식으로 parent[x] = findParent(parent[x])를 하는 이유에 대하여 입니다.

위와 같이 진행하는 이유는, 만약 x == parent[x]가 같지 않다면, 현재 집합이 다른 상태입니다.

그 상황에서 parent[x]의 집합으로 올라가서, 최종 Parent를 찾은 후에 재귀스택이 종료되며 각 속한 집합의 모든 Parent를 최종 Parent의 Index로 동기화 시킬 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[] parent;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	parent = new int[N+1];
    	for(int i=0;i<=N;i++) {
    		parent[i] = i;
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int command = Integer.parseInt(st.nextToken());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		
    		if(command == 0) { //합집합
    			unionFind(a, b);
    		}
    		
    		else if(command == 1) { //같은 집합인지 여부 확인
    			if(findParent(a) == findParent(b)) {
    				System.out.println("YES");
    			}else {
    				System.out.println("NO");
    			}
    		}
    	}
    	
	}
    
    public static int findParent(int x) {
    	if(x == parent[x]) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    public static void unionFind(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	
    	if( a < b) {
    		parent[b] = a;
    	}else if(a >= b) {
    		parent[a] = b;
    	}
    }
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int n, m;
	public static int answer = 0;
	public static int[] parent;
	
	public static int findParent(int x) {
		if( x == parent[x]) return x;
		else return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b ) parent[b] = a;
		else parent[a] = b;
	}
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	m = Integer.parseInt(st.nextToken());
    	
    	parent = new int[n+2];
    	for(int i=0;i<n+2;i++) {
    		parent[i] = i;
    	}
    	
    	for(int i=0;i<m;i++) {
        	st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	int c = Integer.parseInt(st.nextToken());
        	
        	if( a == 0) {
        		unionParent(b, c);
        	}
        	else if( a == 1) {
        		if(findParent(b) != findParent(c)) {
        			System.out.println("NO");
        		}else {
        			System.out.println("YES");
        		}
        	}
    	}
    	
    	
    }
    
}