[Algorithm] 백준 유니온 파인드문제 - 집합의 표현(1717) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드문제 - 집합의 표현 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int cal = parseInt(st.nextToken());
            int a = parseInt(st.nextToken());
            int b = parseInt(st.nextToken());
            
            if (cal == 0) {
                int p1 = find(a); // p1 루트 노드 찾기
                int p2 = find(b); // p2 루트 노드 찾기 
                
                union(p1, p2); // 합치기
            } else {
                boolean same = find(a) == find(b);
                sb.append(same ? "YES" : "NO").append("\n");
            }
        }
        
        System.out.print(sb);
    }
    
    static int find(int child) {

        if (child == parent[child]) return child; // 자신이 루트 노드라면
        return parent[child] = find(parent[child]); // 만약 루트 노드가 아니라면 루트 노드 찾기, 경로압축
    }
    
    static void union(int p1, int p2) {
        parent[p2] = p1; // p2의 부모를 p1으로 바꾸기
    }
}

 

2. 풀이 중점 사항

 

해당 문제는 유니온 파인드를 활용하여 집합을 표현할 수 있습니다.

 

static int find(int child) {

    if (child == parent[child]) return child; // 자신이 루트 노드라면
    return parent[child] = find(parent[child]); // 만약 루트 노드가 아니라면 루트 노드 찾기, 경로압축
}

child의 부모 노드가 자신이라면 이는 곧 루트 노드임을 의미합니다. 따라서, 자기 자신을 그대로 리턴합니다.

하지만, 만약 parent[child]가 자신이 아니라면, 루트 노드가 존재함을 의미합니다.

따라서, 경로 압축을 활용하여 find(parent[child]) 한 값을 찾아서 parent[child]에 대입하고 그 값을 리턴합니다.

 

예를 들어

child = 5;

parent[child] = 3;

parent[3] = 7;

parent[7] = 7 인 상황이 있습니다.

이를 경로 압축을 통해 parent를 찾으면 다음과 같습니다.

 

parent[5] = find(parent[5])  = find(parent[3]) = parent[7]; 이 성립되어 모두 경로를 압축할 수 있습니다.

이를 토대로 시간 복잡도를 효율적으로 개선할 수 있습니다.

 

이상으로 집합의 표현 자바 풀이를 마치도록 하겠습니다. 감사합니다.!