[백준 1717] - 집합의 표현

문제

• 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.
• 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
• 집합을 표현하는 프로그램을 작성하시오.

입력

• 첫째 줄에 n (1 ≤ n ≤ 1,000,000), m (1 ≤ m ≤ 100,000) 이 주어진다.
• m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다.
• 합집합은 0 a b의 형태로 입력이 주어진다.
  • 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다.
• 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다.
  • 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수또는 0이며 같을 수도 있다.

출력

• 1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

솔루션

• 상호 배타적 집합 (Disjoint Set) 을 그대로 구현하면 되는 문제이다.
  • Disjoint Set
• 초기에 각 parent를 본인으로 초기화하고, 합집합 연산을 위한 Union(), 서로 다른 집합인지 확인하는 연산 Find() 만 있으면 된다.

 

Code

• 전체 코드 : Solution1717

public class Solution_1717 {
    static int[] parent, rank;
    static int n;
    
    public static void Swap(int n1, int n2) {
        int temp = n1;
        n1 = n2;
        n2 = temp;
    }
    
    // 현재 원소가 속한 집합의 루트 노드 번호를 출력
    public static int Find(int u) {
        if(u == parent[u]) // 동일하다면 u는 루트노드이므로 그대로 반환
            return u;
        
        return parent[u] = Find(parent[u]); // 경로 압축 최적화
    }
    
    // u, v가 속한 집합을 합쳐주는 연산
    public static void Union(int u, int v) {
        int uR = Find(u);        // u가 속한 집합의 루트 노드를 찾아준다.
        int vR = Find(v);        // v가 속한 집합의 루트 노드를 찾아준다.
        
        if(rank[uR] > rank[vR])  // 일관성을 주기 위해 vR 쪽을 항상 크게 해준다.
            Swap(uR, vR);
        
        parent[uR] = vR;         // 크기가 큰 집합에 작은 집합을 넣어준다.
        
        if(rank[uR] == rank[vR]) // 두 집합의 크기가 동일하다면
            rank[vR]++;          // 한 쪽 집합 크기를 1 증가시켜준다.
    }
}

 

결과

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
NO
NO
YES