[백준] 1717 집합의 표현 - 자바

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

1717번: 집합의 표현

문제 풀이

각 값들이 어떤 집합의 속하는지를 구분하기 위해 집합의 기준이 되는 노드를 정해야 한다. 필자는 가장 작은 값을 그룹의 기준값으로 정하였고 이 로직을 구현하기 위해 union-find 알고리즘을 적용시켰다. union-find에 대한 설명은 이 글을 참고바란다. 

하지만 이 문제에선 바로 합치는 개념이 아니라 0이면 합치고 1이면 그룹의 속해있는지 여부를 알아내야 하기 때문에 기존 union 메소드에서 사이클이 생기는지(= 같은 집합인지)에 대한 검증 로직을 따로 빼내어 unionCheck()메소드를 만들었다

static void union(int a, int b) {
    int aAncestor = findAncestor(a);
    int bAncestor = findAncestor(b);

    // 루트 노드는 작은 값으로 지정
    if (aAncestor > bAncestor)
        ancestor[aAncestor] = bAncestor;
    if (aAncestor < bAncestor)
        ancestor[bAncestor] = aAncestor;

}
static boolean unionCheck(int a, int b) {
    int aAncestor = findAncestor(a);
    int bAncestor = findAncestor(b);

    if (aAncestor == bAncestor) // 같으면 순환
        return true;

    return false;
}

 

코드

package 백준;

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

public class b1717 {
    static int[] ancestor;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // init
        ancestor = new int[N+1];
        for (int i = 1; i <= N; i++) {
            ancestor[i] = i;
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            switch (op) {
                case 0:
                    union(from, to);
                    break;
                case 1:
                    boolean unionFlag = unionCheck(from, to);
                    if (unionFlag) {
                        sb.append("YES\n");
                        break;
                    }
                    sb.append("NO\n");
            }
        }
        System.out.println(sb);
    }

    static void union(int a, int b) {
        int aAncestor = findAncestor(a);
        int bAncestor = findAncestor(b);

        // 루트 노드는 작은 값으로 지정
        if (aAncestor > bAncestor)
            ancestor[aAncestor] = bAncestor;
        if (aAncestor < bAncestor)
            ancestor[bAncestor] = aAncestor;

    }
    static boolean unionCheck(int a, int b) {
        int aAncestor = findAncestor(a);
        int bAncestor = findAncestor(b);

        if (aAncestor == bAncestor) // 같은 집합
            return true;

        return false;
    }

    static int findAncestor(int n) {
        if (n != ancestor[n]) {  // 루트 노드가 아니라면
            ancestor[n] = findAncestor(ancestor[n]);
        }
        return ancestor[n];
    }
}