9. 그래프 이론 - 서로소 집합

공부할 내용

1. 서로소 집합
2. 신장 트리
   • 크루스칼 알고리즘
3. 위상 정렬 (해당 주제는 앞에서 정리했기 때문에 따로 정리하지 않아도 된다.)

공부 방법

• 기타 그래프 이론 - 동빈나 영상 시청 및 정리
• 이것이 코딩테스트다 책 참고
• 추천문제 풀기 (블로그에 문제 풀이를 게시하지는 않겠음)

서로소 집합

• 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미한다.

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
• 서로소 집합 자료구조는 두 종류의 연산을 지원한다.
  • 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
• 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 한다.

여러 개의 합치기 연산이 주어졌을 때, 서로소 집합 자료구조의 동작 과정은 아래와 같다.

1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1) A와 B의 루트 노드 A', B'를 각각 찾는다.
   2) A'를 B'의 부모 노드로 설정한다.
2. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복한다.

서로소 집합 자료구조: 동작 과정

• 처리할 연산들: Union(1,4), Union(2,3), Union(2,4), Union(5,6)
• [초기 단계] 노드의 개수 크기의 부모 테이블을 초기화한다.

• 처리할 연산들: Union(1, 4), Union(2,3), Union(2,4), Union(5,6)
• [Step 1] 노드 1과 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.

• 처리할 연산들: Union(1, 4), Union(2,3), Union(2,4), Union(5,6)
• [Step 2] 노드 2과 노드 3의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 3이므로 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정한다.

• 처리할 연산들: Union(1, 4), Union(2,3), Union(2,4), Union(5,6)
• [Step 3] 노드 2와 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 1이므로 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.

여기서 주의해야할 점은 3번 노드와 4번 노드는 실제로 같은 집합에 포함되어있지만, 3번 노드는 현재 부모 노드가 '2'로 아직 업데이트가 되지 않았다.
3번 노드의 부모를 확인한 뒤에 2번 노드가 나오고 다시 한번 2번 노드의 부모를 확인해서 1번 노드가 나오고, 1번 노드의 부모는 1번이기 때문에 최종적으로 부모 노드가 1번이라고 판단하게 해야한다.

• 처리할 연산들: Union(1, 4), Union(2,3), Union(2,4), Union(5,6)
• [Step 4] 노드 5와 노드 6의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 5와 6이므로 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정한다.

주의사항

• 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
  • 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.
• 다음 예시에서 노드 3의 루트를 찾기 위해서는 노드 2를 거쳐 노드 1에 접근해야 한다.

서로소 집합 자료구조: 기본적인 구현 방법

public class FindParent {

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int[] parent, int x) {

        if (parent[x] != x) {
            return findParent(parent, parent[x]);
        }

        return x;
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int[] parent, int a, int b) {
        a = findParent(parent, a);
        b = findParent(parent, b);

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

        parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 노드의 개수와 간선(Union 연산)의 개수 입력 받기
        int v = sc.nextInt();
        int e = sc.nextInt();

        // 부모 테이블 초기화하기
        int[] parent = new int[v + 1];

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        // Union 연산을 각각 수행
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            unionParent(parent, a, b);
        }

        // 각 원소가 속한 집합 출력하기
        System.out.println("각 원소가 속한 집합 ");
        for (int i = 1; i <= v; i++) {
            System.out.print(findParent(parent, i) + ' ');
        }
        System.out.println();

        System.out.println("부모 테이블 내용 출력하기");
        for (int i = 1; i <= v ; i++) {
            System.out.print(parent[i] + ' ');
        }
        System.out.println();
    }

}

기본적인 구현 방법의 문제점

수행시간 측면에서 문제를 가지고 있다.

• 합집합(Union) 연산이 편향되게 이루어지는 경우 찾기(Find) 함수가 비효율적으로 동작한다.
• 최악의 경우에는 찾기(Find) 함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(V)가 된다.
  • 다음과 같이 {1, 2, 3, 4, 5}의 총 5개의 원소가 존재하는 상황을 확인해보자.
  • 수행된 연산들: Union(4, 5), Union(3, 4), Union(2, 3), Union(1, 2)

해결책: 경로 압축

• 찾기(Find) 함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.
  • 찾기(Find) 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.

// 특정 원소가 속한 집합을 찾기 (경로 압축 버전)
    public static int upgradeFindParent(int[] parent, int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출하여 바로 부모 테이블의 값을 갱신
        if (parent[x] != x) {
            parent[x] =  findParent(parent, parent[x]);
        }

        return parent[x];
    }

• 경로 압축 기법을 적용하면 각 노드에 대하여 찾기(Find) 함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 된다.
• 동일한 예시에 대해서 모든 합집합(Union) 함수를 처리한 후 각 원소에 대하여 찾기(Find) 함수를 수행하면 다음과 같이 부모 테이블이 갱신된다.
• 기본적인 방법에 비하여 시간 복잡도가 개선된다.

서로소 집합을 활용한 사이클 판별

• 서로소 집합을 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
  • 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.
• 사이클 판별 알고리즘은 다음과 같다.
  1. 각 간선을 하나씩 확인하여 두 노드의 루트 노드를 확인한다.
     1) 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행한다.
     2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

동작 과정

• [초기 단계] 모든 노드에 대하여 자기 자신을 부모로 설정하는 형태로 부모 테이블을 초기화한다.

• [Step 1] 간선 (1, 2)를 확인한다. 노드 1과 노드 2의 루트 노드는 각각 1과 2이다. 따라서 더 큰 번호에 해당하는 노드 2의 부모 노드를 1로 변경한다.

• [Step 2] 간선 (1, 3)를 확인한다. 노드 1과 노드 3의 루트 노드는 각각 1과 3이다. 따라서 더 큰 번호에 해당하는 노드 3의 부모 노드를 1로 변경한다.

• [Step 3] 간선 (2, 3)를 확인한다. 노드 2와 노드 3의 루트 노드는 모두 1이다. 다시 말해 사이클이 발생한다는 것을 알 수 있다.

서로소 집합을 활용한 사이클 판별

public class CycleVerifier {

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int[] parent, int x) {
        // 루트 노드를 찾을 때까지 재귀 호출
        if (parent[x] != x) {
            parent[x] = findParent(parent, x);
        }

        return parent[x];
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int[] parent, int a, int b) {
        a = findParent(parent, a);
        b = findParent(parent, b);
        if (a < b) {
            parent[b] = a;
            return;
        }

        parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 노드의 개수와 간선의 개수 입력 받기
        int v = sc.nextInt();
        int e = sc.nextInt();
        int[] parent = new int[v + 1];

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

        boolean cycle = false; // 사이클 발생 여부!

        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            // 사이클이 발생한 경우 종료
            if (findParent(parent, a) == findParent(parent, b)) {
                cycle = true;
                break;
            }

            unionParent(parent, a, b);
        }

        if (cycle) {
            System.out.println("사이클이 발생했습니다.");
            return;
        }

        System.out.println("사이클이 발생하지 않았습니다.");
    }
}