문제 설명

문제 분석

<aside> 💡 유니온 파인드에서 자주 실수하는 부분

1. find 연산을 수행할 때 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 이번 연산에서 발견한 대표 노드로 변경하는 부분 (=경로압축)
2. union 연산에서 선택된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결하는 부분 </aside>

슈도코드

구현

public class 집합_표현하기_1717 {
    static int[] parent;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(); //원소 개수
        int M = scan.nextInt(); // 질의 개수
        parent = new int[N+1]; // 대표 노드 배열
        for (int i = 0; i < N+1; i++) {
            parent[i] = i;
        }

        // 질의 계산
        for (int i = 0; i < M; i++) {
            int question = scan.nextInt();
            int a = scan.nextInt();
            int b = scan.nextInt();
            if(question == 0) { // union
                union(a, b);
            } else { // 두 원소 같은지 판별
                boolean result = isSame(a, b);
                if (result) {
                    // 연결이 되었다는 뜻
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    private static void union(int a, int b) {
        // TODO: 중요!! 대표노드 찾아서 연결
        a = find(a);
        b = find(b);
        if(a != b) {
            parent[b] = a; // 두 노드 연결
        }
    }

    private static int find(int a) {
        if(a == parent[a]) { // 대표노드(인덱스 == 값)인지 확인
            return a;
        } else {
            // TODO: 중요!! 재귀가 끝나고 그 값을 그때의 대표노드 값으로 업데이트
            return parent[a] = find(parent[a]); // value를 인덱스로 변경해서 다시 찾음
        }
    }

    private static boolean isSame(int a, int b) {
        a = find(a);
        b = find(b);
        return a == b;
    }
}