[백준] 1717번 : 집합의 표현 - 자바(Java)

Problem 🔒

문제

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

 

초기에 n+1개의 집합 {0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

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

출력

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제한

• 1≤n≤1000000
• 1≤m≤100000
• 0≤a,b≤n
• a, b는 정수
• a와 b는 같을 수도 있다.

예제 입력 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

예제 출력 1

NO
NO
YES

---

Approach 1 ⭕ - 최적화 없는 유니온 파인드

유니온 파인드 알고리즘을 활용하여 풀 수 있는 문제이다.

1. 입력
   • 일단 입력 개수가 10만개가 넘어가기 때문에, BufferedReader를 사용했다.
   • Union-Find 연산을 하기 위해, 집합을 배열로 생성하고 모두 -1로 채웠다.
   • 합집합 연산(0)이 주어지면, uni( ) 함수를 호출한다.
   • 같은 집합인지 확인하는 연산(1)이 주어지면, check( ) 함수를 호출한다.
   • 최종적으로 연산의 결과를 StringBuilder에 저장하여 한 번에 출력한다.
2. 루트노드를 찾는 연산 : find(int x) 메서드
   • 재귀를 활용하여, 자신의 부모 노드로 타고 루트 노드까지 올라간다.
   • 현재의 노드 값이 음수이면, 루트노드임을 의미하므로 현재 노드를 리턴한다.
3. 합집합 연산 : uni(int u, int v) 메서드
   • u의 루트노드를 find( )를 사용해 구한다.
   • v의 루트노드도 find( )를 사용해 구한다.
   • u의 루트노드와 v의 루트노드가 같으면 무시한다.
   • 두 루트노드가 같지 않으면, v가 속한 트리의 루트를 u가 속한 트리의 루트 자식으로 만든다.
4. 같은 집합인지 확인 : check(int u, int v) 메서드
   • u와 v의 루트노드를 find( )를 사용해 구한다.
   • 부모노드가 같으면 “yes”, 아니면 “no”를 StringBuilder에 추가한다.

Approach 2 ⭕ - Union By Rank 최적화

Union By Rank 최적화는 집합 트리의 높이를 고려해서 집합을 합치는 방법이다.

합집합 연산을 담당하는 uni(int u, int v) 메서드를 수정한다.

1. 먼저, u와 v의 루트노드를 find()를 사용해 구한다.
2. 루트노드가 서로 일치한다면 무시한다. (문제에서 같은 원소도 주어질 수 있다고 한다.)
3. u의 트리를 a, v의 트리를 b라고 한다면, a 트리의 높이가 더 높게 설정한다.
   • 집합 배열에서 루트노드에 트리의 높이를 저장할 것이다.
   • 배열에서 -1 값이 의미하는 것은 높이가 1인 트리이다.
   • 그렇기에 u의 루트노드 값과 v의 루트노드 값을 비교하면 어느 집합의 높이가 더 높은지 알 수 있다.
   • 루트노드에 저장된 값이 더 작을수록 트리의 높이가 높은 것이다.
4. 트리의 높이가 같다면 한 쪽 트리(a)의 값을 감소시켜, 트리의 높이를 증가시킨다.
   • 트리의 높이가 같을 때, 집합을 합친다면 트리의 높이가 1 높아진다.
5. 마지막으로, v가 속한 트리의 루트를 u가 속한 트리의 루트 자식으로 만든다.

Approach 3 ⭕ - 경로 압축 최적화

경로 압축 최적화는 루트노드를 찾을 때, 경로를 압축하여 효율적으로 루트노드를 찾는 방법이다.

루트노드를 찾는 연산을 담당하는 find(int x) 메서드를 수정한다.

1. 현재의 노드 값이 음수이면, 루트노드임을 의미하므로 현재 노드를 리턴하는 것은 동일하다.
2. 재귀를 활용하여, 자신의 부모노드를 타고 올라가면서 만난 노드의 부모를 루트노드로 변경한다.
   • 예를들어, 3-4-5-6 트리에서 3의 부모가 4, 4의 부모가 5, 5의 부모가 6, 6이 루트노드라고 한다면
   • 3의 부모, 4의 부모를 루트노드인 6으로 변경하여 루트노드를 찾는 경로를 압축한다.

 

최적화하지 않은 유니온파인드보다, 최적화한 것이 훨씬 효율적이었다.

이론상 경로압축 최적화가 더 실행시간이 빠르다고 알고 있지만, 이 문제에서는 비슷했다.

실전에서 특이점이 없다면 경로 압축 최적화가 코드가 간결해 더 많이 적용할 것 같다.

---

Solution 💡

최적화 없는 유니온 파인드

public class Main {
    static int N, M, tree[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken())+1;
        M = Integer.parseInt(st.nextToken());
        tree = new int[N];
        Arrays.fill(tree, -1);
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int o = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (o == 0) uni(a, b); // 합집합
            else check(a, b); // 같은 집합인지 확인
        }
        System.out.println(sb);
    }
    public static void check(int u, int v){
        int a = find(u);
        int b = find(v);
        sb.append(a==b?"yes":"no").append("\\n");
    }

    public static int find(int x){
        if(tree[x]<0) return x; // 루트 노드이면 반환
        return find(tree[x]);
    }

    public static void uni(int u, int v){
        int a = find(u);
        int b = find(v);
        if(a!=b) tree[b]=a;
    }
}

union by rank 최적화

public static void uni(int u, int v){
  int a = find(u); // u의 루트노드
  int b = find(v); // v의 루트노드
  if(a==b) return; // 두 원소가 같으면 넘어간다.
  // union by rank : 높이가 더 높은 트리로 합친다.
  // 루트노드의 값(트리의 높이) 비교하여, a가 더 작은 값이 되도록한다.
  // 즉, a가 더 높은 트리가 되도록 설정한다. 
  if(tree[b]<tree[a]){
      int tmp = a;
      a = b;
      b = tmp;
  }
  // 위의 if문으로 인해 (a의 높이 >= b의 높이)
  // 트리의 높이가 같다면, 트리의 높이가 1증가한다는 의미이다.
  if(tree[a]==tree[b]) tree[a]--;
  tree[b] = a;
}

경로 압축 최적화

public static int find(int x){
    if(tree[x]<0) return x;
    // 경로 압축 최적화
    return tree[x] = find(tree[x]);
}

union by rank & 경로 압축 최적화

public static int find(int x){
    if(tree[x]<0) return x;
    // 경로 압축 최적화
    return tree[x] = find(tree[x]);
}

public static void uni(int u, int v){
    int a = find(u);
    int b = find(v);
    if(a==b) return;
    // union by rank 최적화
    if(tree[b] < tree[a]){
        int tmp = a;
        a = b;
        b = tmp;
    }
    if(tree[a]==tree[b]) tree[a]--;
    tree[b] = a;
}

알게된 점 😯

유니온 파인드 연산의 기본 메커니즘을 이해하게 되었다.

최적화 방법으로 union by rank, 경로 압축을 배웠다.

• union by rank : union할 때, 트리의 높이가 더 높은 트리로 합치기
• 경로 압축 : find 할 때, 부모 노드를 루트 노드로 변경하여 트리의 높이를 낮추기