[백준] 1717번 집합의 표현 (JAVA)

문제

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

1717번: 집합의 표현

 

설명

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

각 (n + 1) 개의 집합은 서로소 집합이다.

합집합 연산이 필요할 때에는 union()를 사용하고 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산이 필요할 때에는 find()을 사용해 두 원소의 대표 번호를 비교한다.

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

union(a, b)에서는 a, b의 대표 번호를 확인해서 다를 경우 a의 부모 노드 값에 b를 넣는다.

find(a)에서는 a의 부모 노드가 자기 자신인지 확인하고 아니라면 해당 부모 노드를 따라 최종 부모 노드까지 탐색한다.

void union(int a, int b) {
    // element1과 element2의 대표 노드 확인
    int root1 = find(a);
    int root2 = find(b);

    // element1과 element2의 대표 노드가 다를 경우
    if (root1 != root2)
        parent[root1] = root2;
}

int find(int a) {
    // 찾는 대상과 인덱스 번호가 같다면 그 인덱스가 해당 집합의 부모이다
    if (parent[a] == a)
        return a;
    else {
        // 해당 인덱스가 가리키는 값(부모 노드)을 따라 최종 부모 노드까지 탐색
        return parent[a] = find(parent[a]);
    }
}

 

전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[] parent;

    static void union(int a, int b) {
        // element1과 element2의 대표 노드 확인
        int root1 = find(a);
        int root2 = find(b);

        // element1과 element2의 대표 노드가 다를 경우
        if (root1 != root2)
            parent[root1] = root2;
    }

    static int find(int a) {
        // 찾는 대상과 인덱스 번호가 같다면 그 인덱스가 해당 집합의 부모이다
        if (parent[a] == a)
            return a;
        else {
            // 해당 인덱스가 가리키는 값(부모 노드)을 따라 최종 부모 노드까지 탐색
            return parent[a] = find(parent[a]);
        }
    }

    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 num = 1; num <= N; num++) {
            parent[num] = num;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int flag = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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