유니온 파인드. 집합의 표현

문제

0~n까지 {0}, ... , {n} 형태인 집합이 표시되는데, 0이면 서로 합하고, 1이면 서로 같은 집합에 속하는지 확인하는 문제이다.

해결방향성

0: union, 1: find로 나누어서 풀면된다. 기본적으로 합할 두원소를 from, to로 두고, 각각 포함된 루트를 찾는다. 둘이 루트가 일치하면 둘은 같은 집합에 속하는 것으로 부모노드를 갱신하지않고 그냥 리턴한다. 다른 경우 연결해준다.
그리고, find함수는 union 부분에서 루트가 같으면 true, 틀리면 false로 리턴해주면된다.

코드

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

public class Main {
    static int n, m;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        parent = new int[n + 1]; // 0 ~ n까지 부모 확인
        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 from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            int fromParent = findParent(from);
            int toParent = findParent(to);

            if (command == 0) { // 합함.
                union(fromParent, toParent);
            }
            if (command == 1) { // 확인. -> 부모노드 같은지 확인
                if(find(fromParent, toParent)){
                    bw.write("YES\n");
                }
                else{
                    bw.write("NO\n");
                }

            }
        }


        bw.flush();
        br.close();
        bw.close();
    }

    private static void union(int fromParent, int toParent) {
        if (fromParent == toParent) return;
        parent[toParent] = fromParent; // 부모노드 갱신
    }

    private static boolean find(int fromParent, int toParent) {
        if (fromParent == toParent) {
            return true;
        } else {
            return false;
        }
    }

    private static int findParent(int node) {
        if (parent[node] == node) return node; // 끝 도달
        return parent[node] = findParent(parent[node]); // 부모노드로 계속 재귀.
    }
}

결론

사실 알고 풀어서 그렇지, 몰랐으면 유니온 파인드로 쉽게 해결가능하다는걸 몰랐을듯. 사실 findParent만 잘짜도 해결가능. (알고 짜기)