유니온 파인드, 집합의 표현(백준_1717)

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

1717번: 집합의 표현

 

문제 설명

{0} {1} {2} .... {n}이 주어지고 각가 쿼리가 주어진다.

• 입력값이 0 a b 일 경우 a와 b를 합쳐라!
• 입력값이 1 a b 일 경우 a와 b가 같은 집합에 포함되어 있는지를 확인하는 것이다.

예시로 살펴보면 7일경우 {1} {2} {3} {4} {5} {6} {7} 이 존재한다. 0 1 3일 경우 {1,3} {2} {4} {5} {6} {7} 이 된다.

1 1 7일 경우 1 과 7은 같은 집합에 존재하지 않으므로 NO가 출력된다.

 

문제에 대한 아이디어

유니온 파인드를 구현하는 문제이다.

유니온 파인드 알고리즘은 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 한다.  

일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있다.

• Union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b 가 a ∈ A, b ∈ B 일 때 union(a, b)는 A ∪ B를 말한다.
• Find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A 일 때 find(a)는 A 집합의 대표 노드를 반환한다.

 

유니온 파인드 과정 살펴보기 (Do it! 알고리즘 코딩 테스트 자바 편)

1. 유니온 파인드는 1차원 배열을 이용하여 표현한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 

 

2. 1 과 4와 5와 6을 union 연산한다고 하자.

1은 대표 노드 4는 자식 노드가 된다. 또 5는 대표노드 6은 자식노드가 된다. 자식 노드 인덱스의 값은 대표 노드의 인덱스로 바꾼다.

 

3. 4, 6 을 union 연산한다고 하자.

4가 대표 노드 6이 자식 노드로 가야 한다. 4와 6이 자식노드이기 때문에 각각 대표노드로 올라간다 그 후 대표노드 끼리 자식 노드와 대표 노드를 선정해 준다. 

 

Union 연산만할 경우 문제점

위의 마지막 단계를 트리로 나타내면 위의 그림처럼 나타난다. 하지만 이럴 경우 문제점이 존재한다. 우리는 1과 6이 연결된 걸 알 고 있지만 탐색을 하려면 최악의 경우 O(N) 이 필요할 수 있다.

 

해결책

find 연산을 실행 한다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상한다.

1. 대상 노드 배열에 index값과 value값이 동일한지 확인한다.
2. 동일하지 않으면 value값이 가리키는 index위치로 이동한다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 1,2번을 반복한다. (재귀로 구현)
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경한다.

Find(6)을 실행한 후

이렇게 하면 find(6)을 할 경우 O(1) 만에 탐색이 가능해진다!!

이렇게 find를 통해 자신의 루트 노드로 자신의 배열 값을 바꾸는 것을 경로 압축이라고 한다.

경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법이다.

 

구현

• Main 함수

static int arr[];
public static void main(String []args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    arr= new int[n+1];
    for(int i =0; i<=n; ++i){
        arr[i] = i;
    }
    for(int i = 0; i <m; ++i){
        st = new StringTokenizer(buf.readLine());
        int t = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        if(t == 0){
            union(a,b);
        }
        else{
            if(find(a) == find(b)) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

• find 함수

public static int find(int a){
    if(arr[a] == a) return a;
    else{
        return arr[a] = find(arr[a]); //리턴하면서 자신이 지금까지 왔던 모든 index를 루트노드 값으로 바꿈
    }
}

• union 함수

public static void union(int a, int b){
    a = find(a);
    b = find(b);
    if(a == b) return;
    arr[b] = a;
}

크루스칼의 알고리즘에서 쓰이는 부분은 cycle인지 검사할 때 쓰인다. 받은 노드 2개를 계속 union 한다. union 하기 전에 find를 하면서 만약 루트노드가 같으면 2개의 노드는 이어져있다는 것이므로 cycle이 된다.

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_1717.java

GitHub - Heron-Woong/CodingTest_Practice