BOJ G5 1717 집합의 표현 JAVA

1717번: 집합의 표현

---

문제 읽기

이전이었으면 이게 뭐지.. 하면서 끙끙댔을 테지만, 어제 유니온 파인드를 공부했기 때문인지, 읽자마자 이건 그냥 유니온 파인드라는 생각이 들었다.

 

유니온 파인드에 대해 개념을 알고 싶으면 우선 이 포스팅을 먼저 보고 오길 추천한다.

분리 집합, Disjoint Set : Union-Find

 

---

코드

딱히 풀이는 없다. 바로 코드를 보자.

package ps.ㄱSolving;

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

public class BOJ_G5_1717_집합의표현 {
    static int N, M;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        parent = new int[N+1]; //0~N
        //우선은 각각 별개의 집합이므로 루트를 자기 자신으로 초기화
        for (int i = 0; i < N+1; i++) {
            parent[i] = i;
        }

        //logic
        StringBuilder sb = new StringBuilder();
        while(M-- > 0){
            st = new StringTokenizer(in.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            //집합 합치기
            if (cmd == 0) union(a, b);
            //같은 집합인지 확인
            else {
                boolean isSame = (find(a) == find(b));
                sb.append((isSame)? "YES" : "NO").append("\\n");
            }
        }
        System.out.println(sb);
    }

    private static int find(int a) { //루트를 찾아주는 함수
        if (a == parent[a]) return a;

        return parent[a] = find(parent[a]); //루트를 찾으며 루트로 부모를 갱신(트리의 높이 낮추기)
    }

    private static void union(int a, int b) { //집합을 합치는 함수
        int pa = find(a);
        int pb = find(b);

        if (pa != pb){
            //다른 집합인 경우 합치기
            parent[pa] = pb;
        }
    }
}

 

사실 실수한 부분이 있었다.

실수한 부분

union : 두 집합을 합칠 때는 대표 원소끼리 합쳐야 한다

처음에 union을 이렇게 작성했었다

    private static void union(int a, int b) { //집합을 합치는 함수
        int pa = find(a);
        int pb = find(b);

        if (pa != pb){
            //다른 집합인 경우 합치기
            parent[a] = parent[b];
        }
    }

 

하지만 유니온 파인드 개념 포스팅에서도 작성했듯이, 대표 원소끼리 합쳐야 한다. 즉, 대표 원소란 최상위 루트, 즉 위 코드에서는 pa, pb로 각각 표현되어 있다. 이 때문에 7퍼센트에서 틀렸었는데, 아래와 같이 고치니 정답이었다.

    private static void union(int a, int b) { //집합을 합치는 함수
        int pa = find(a);
        int pb = find(b);

        if (pa != pb){
            //다른 집합인 경우 합치기
            parent[pa] = pb;
        }
    }