[알고리즘] 유니온과 파인드 알고리즘(union, find)

Union과 find는 집합과 관련된 연산이다.

 

- Union : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산

- find : 두 노드가 같은 집합에 속해 있는 지를 확인하는 연산

 

 

코드 상에서의 구현 방법도 어렵지 않다.

 

일반적으로 유니온과 파인드를 구현하기 위해 1차원 배열을 사용한다.

초기에는 아무 노드도 연결되어 있지 않기 때문에 각 노드가 대표노드가 되며 자신의 인덱스 값으로 초기화 된다.

 

 

union은 두 노드의 대표노드를 일치시키는 연산이다.

이 과정에서 재귀적으로 대표노드를 찾는 과정이 포함될 수 있다.

 

find는 자신이 속한 집합의 대표노드를 찾는 연산이다.

이 과정이 중요한 이유는 단순히 노드를 찾을 뿐만 아니라, 그래프를 정돈하고 시간 복잡도를 향상시키기 때문이다.

 

 

 

그렇다면, find의 어떠한 과정이 그래프를 정돈하고 시간복잡도를 향상시킬까?

 

>  대표노드를 찾는 과정(즉, 재귀 함수를 거치며)에서 각 노드의 대표노드를 제일 마지막에 도달하는 대표노드로 변경하기 때문이다. 이는 결국 추후의 대표노드를 찾는 연산 속도가 O(1)로 바뀌는 경로 압축의 효과로드러난다.

 

 

 

문제를 통해 유니온과 파인드를 구현해보자.

 

 

 

Union, Find 예시 문제 1

 

 

1717번: 집합의 표현

 

해당 문제는 최대 원소 개수가 1,000,000이고, 질의 개수가 100,000으로 큰 편이다. 그래서 경로 압축이 필요한 대표적인 유니온 파인드 문제라고 할 수 있다.

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static int[] parent;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        parent = new int[N+1];
        for(int i=0; i<=N; i++) {
            parent[i] = i;
        }

        for(int i=0; i<M; i++) {
            int question = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (question == 0) {
                union(a, b);
            } else {
                if (checkSame(a, b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }
    public static int find(int a) {
        if (a == parent[a]) {
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }
    }
    public static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return true;
        }
        return false;
    }
}

 

 

 

 

- parent라는 1차원 배열을 통해 대표노드에 관련한 정보를 저장한다.

- parent[i] = i를 저장함으로써, 초기에 대표노드를 자기 자신으로 초기화한다.

- union 함수는 각 노드에 대한 대표노드를 찾고, 같지 않을 시에 같도록 해준다.

- find 함수는 대표노드가 자기 자신 인덱스와 같을 때는 초기화된 상태 그대로 이므로 인덱스를 리턴해주지만, 아닐 경우에는 find 함수를 재귀적으로 호출하여 대표노드를 찾는다. 이 과정에서, parent[a] 에 재귀함수의 리턴값을 주어 경로 압축의 효과를 볼 수 있다.

 

 

 

Union, Find 예시 문제 2

 

1976번: 여행 가자

 

 

해당 문제는 도시의 연결 유무를 유니온과 파인드를 이용해야 한다는 아이디어를 떠올리면 쉽게 풀 수 있는 문제이다.

도시의 수에 대해서는 대표노드 1차원 배열을 사용하고, 인접 행렬을 탐색하면 된다.

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static int[] parent;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[][] dosi = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            for(int j = 1; j<=N; j++) {
                dosi[i][j] = sc.nextInt();
            }
        }

        int[] route = new int[M+1];
        for(int i=1; i<=M; i++) {
            route[i] = sc.nextInt();
        }

        parent = new int[N+1];
        for(int i=1; i<=N; i++) {
            parent[i] = i;
        }



        for(int i=1 ; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if (dosi[i][j] == 1) union(i, j);
            }
        }

        int index = find(route[1]);
        for(int i=2; i<route.length; i++) {
            if (index != find(route[i])) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a!=b) {
            parent[b] = a;
        }
    }

    public static int find(int a) {
        if (a == parent[a]) {
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }
    }

}

 

 

-  parent[i] = i로 대표노드를 자기 자신으로 초기화 시켜준다.

- 인접 행렬에서 도시가 연결되어 있다면, union을 실행한다. > union(i, j)

- 여행 계획 도시들이 1개의 대표 도시로 연결되어 있는 지 확인한다. index = find(route[1])

 

 

 

 

Union, Find 예시 문제 3

 

 

1043번: 거짓말

 

 

 

import java.util.*;
import java.io.*;

public class Main {

    static int[] parent;
    static int[] trueP;
    static ArrayList<Integer>[] party;
    static int result;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();

        result = 0;
        trueP = new int[T];
        for(int i=0; i<T; i++) {
            trueP[i] = sc.nextInt();
        }

        party = new ArrayList[M];
        for(int i=0; i<M; i++) {
            party[i] = new ArrayList<Integer>();
            int party_size = sc.nextInt();
            for(int j=0; j<party_size; j++) {
                party[i].add(sc.nextInt());
            }
        }

        parent = new int[N+1];
        for(int i=0; i<=N; i++) {
            parent[i] = i;
        }


        for(int i=0; i<M; i++) {
            int firstPeople = party[i].get(0);
            for(int j=1; j<party[i].size(); j++) {
                union(firstPeople, party[i].get(j));
            }
        }

        for(int i=0; i<M; i++) {
            boolean isPossible = true;
            int cur = party[i].get(0);
            for(int j=0; j<trueP.length; j++) {
                if(find(cur) == find(trueP[j])) {
                    isPossible = false;
                    break;
                }
            }
            if (isPossible) result++;
        }
        System.out.println(result);
    }

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

    public static int find(int a) {
        if (a == parent[a]) {
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }

    }





}

 

 

- 진실을 아는 사람들을 각각 하나의 집합으로 보아야 한다.

- 각 파티에 참석한 사람들을 같은 집합으로 보고, 진실을 아는 사람들의 집합에 속해 있는 지 확인한다.

- 각 파티에 참석한 사람들을 union을 통해 대표노드를 같게 만든다.

- 진실을 아는 사람들의 집합과 각 파티의 집합의 대표노드를 비교하여, 갈 수 있는 파티인 지 확인한다.

 

 

 

Reference

- Do it! 코딩 테스트 - 실전 편