BJ G5 1717 집합의 표현

알고리즘/유니온-파인드

BJ G5 1717 집합의 표현 - Java

naksnaks 2024. 10. 9. 20:54

[문제링크]

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

[문제]

초기에 n+1개의 집합 {0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

[입력]

첫째 줄에 n, m이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

[출력]

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

[예제 입력 1]

[예제 출력 1]

NO
NO
YES

[설명]

처음에 BFS로 풀려고 했다. 하지만 시간 초과가 나오게 되었고, 결국 어떻게 푸는지 검색을 하게 되었다.이 문제는 유니온파인드의 유형으로 합집합, 서로소집합 등과 관련된 문제일 경우, 유니온파인드를 사용하면 된다.

유니온 함수와 파인드 함수 두개를 만들어야 한다.

void union( int x, int y) {

	// x의 루트 노드와 y의 루트 노드를 찾는다.
	int a = find(x);
    int b = find(y);
    
    // 루트노드가 다르다면 b의 루트 노드를 a로 변경시키며 트리를 합친다.
    if( a != b ) {
    	parent[b] = a;
    }
}

// 루트를 찾아가는 과정
int find( int x ) {
	if( parent[x] == x ) { // x가 루트 노드임.
    	return x;
    }
    return parent[x] = find(parent[x]);  // x가 루트가 아닐경우 x의 부모로 한칸 이동한다.
}

a와 b의 루트가 같은지 확인한 후, 같으면 YES, 다르면 NO를 출력한다.

백준 알고리즘 1717번 JAVA풀이

import java.util.*;

public class BJ1717 {

    static int[] parent;

    static int find(int x){
        if(parent[x] == x){
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    static void union(int x, int y) {
        int a = find(x);
        int b = find(y);
        if(a!=b){
            parent[b] = a;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        parent = new int[N+1];

        for(int i=1;i<=N;i++){
            parent[i] = i;
        }

        for(int i=0;i<M;i++){
            int flag = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();

            if(flag==0){
                union(a, b);
            }else{
                if(find(parent[a])==find(parent[b])){
                    System.out.println("YES");
                }else{
                    System.out.println("NO");
                }
            }
        }
    }
}