서로소 집합(Disjoint Set: Union-Find)과 크루스칼, 프림 알고리즘

📝 Union-Find 알고리즘

서로소 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘으로, 트리 구조를 활용

간단하게, 노드들 중에 연결된 노드를 찾거나 혹은 노드들을 서로 연결할 때 사용

 

📌 서로소 집합(Disjoint Set)이란?

• 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 공통 원소가 없는 상호 배타적(서로소)인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미

 

📌 흐름

1.초기화

n개의 원소가 최초엔 개별 집합으로 이루어지도록 초기화

 

2.Union

두 개별 집합을 하나의 집합을 합침(두 트리를 하나의 트리로 만듦)

 

3.Find

여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 각 그룹의 최상단 원소 즉, 루트 노드)를 확인

 

📌 Union-Find 알고리즘의 고려할 점

• Union 순서에 따라서, 최악의 경우 링크드 리스트와 같은 형태가 될 수 있음
• 이 때는 Find/Union 시 계산량이 O(N)이 될 수 있으므로, 해당 문제를 해결하기 위해 union-by-rank, path compression 기법을 사용함

 

union-by-rank 기법

• 각 트리에 대해 높이(rank)를 기억해 두고,
• union 시에 두 트리의 높이(rank)가 다르면 높이가 작은 트리를, 높이가 큰 트리에 붙임
• 즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함

 

path compression 기법

• find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
• find를 실행한 노드는 이후부터는 루트 노드를 한 번에 알 수 있음

 

👉 union-by-rank와 path compression 기법 사용 시, 시간 복잡도는 다음 계산식을 만족함이 증명되었음!

• $O(Mlog*N)$
• $log*N$은 다음 값을 가짐이 증명되었음
  • $N$이 $2^{65536}$값을 가지더라도, $log*N$의 값이 5의 값을 가지므로, 거의 $O(1)$ 즉 상수값에 가깝다고 볼 수 있음

$N$	$log*N$
1	0
2	1
4	2
16	3
65536	4
$2^{65536}$	5

 

📌 예시 문제

오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다.

모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다.

만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.

학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.

두 학생이 친구이면 "YES"이고, 아니면 "NO"를 출력한다.

 

입력 설명

첫 번째 줄에 반 학생수인 자연수 N(1 <=N <=1,000)과 숫자쌍의 개수인 M(1 <=M <=3,000)이 주어지고,

다음 M개의 줄에 걸쳐 숫자쌍이 주어진다.

마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.

 

출력 설명 

첫 번째 줄에 "YES" 또는 "NO"를 출력한다.

 

입력 예제

9 7
1 2
2 3
3 4
1 5
6 7
7 8
8 9
3 8

 

출력 예제

NO

 

구현 코드

import java.util.*;

public class Main {
    static int[] parent;
    static int[] rank;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

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

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            union(a, b);
        }

        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int fa = find(a);
        int fb = find(b);

        if (fa == fb) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    public static int find(int node) {
        // path compression 기법
        if (node == parent[node]) {
            return parent[node];
        } else {
            return parent[node] = find(parent[node]);
        }
    }

    public static void union(int node_v, int node_u) {
        int root1 = find(node_v);
        int root2 = find(node_u);
        
        // union-by-rank 기법
        if (rank[root1] > rank[root2]) {
            parent[root2] = root1;
        } else {
            parent[root1] = root2;
            if (rank[root1] == rank[root2]) {
                rank[root2] += 1;
            }
        }
    }
}

 

📝  최소 신장 트리의 이해

📌 신장 트리(Spanning Tree)란?

원래의 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프

• 신장 트리의 조건
  • 원래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결되어 있어야 함
  • 트리의 속성을 만족시켜야 함 (즉, 사이클이 존재하지 않아야 함)
   

 

최소 신장 트리 (Minimum Spanning Tree, MST)

가능한 신장 트리 중에서, 간선의 가중치 합이 최소인 신장 트리를 지칭함

 

최소 신장 트리 알고리즘

• 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함
• 대표적인 최소 신장 트리 알고리즘
  • Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘)

 

📌 최소 신장 트리 알고리즘

크루스칼 알고리즘과 프림 알고리즘 비교

• 둘 다 그리드 알고리즘을 기초로 하고 있음 (당장 눈앞의 최소 비용을 선택해서, 결과적으로 최적을 솔루션을 찾음)
• 크루스칼 알고리즘은 가장 가중치가 작은 간선부터 선택하면서, 최소 신장 트리를 찾음
  • 정렬 및 Union-Find 알고리즘
• 프림 알고리즘은 특정 정점에서 시작하여 해당 정점에 연결된 가장 가중치가 작은 간선을 선택하면서, 최소 신장 트리를 찾음
  • 무방향 인접리스트, 우선순위 큐 사용

 

크루스칼 알고리즘(Kruskal's algorithm)

1. 모든 정점을 독립적인 집합으로 만든다.
2. 모든 간선을 비용 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.
   • 최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것!
   • 쉽게 말해서 Union-Find 알고리즘을 사용해서, 같은 집합이 아닌 경우에만 연결해 나가는 것이다.

 

👉 크루스칼 알고리즘은 그리드 알고리즘을 기초로 하고 있다.

     즉, 당장 눈앞의 최소 비용을 선택해서 결과적으로 최적의 솔루션을 찾는 것이다!

 

✨ 시간 복잡도

• 크루스칼 알고리즘의 시간 복잡도는 $O(ElogE)$
  • 다음 단계에서 2번, 간선을 비용을 기준으로 정렬하는 시간에 좌우됨
    1. 모든 정점을 독립적인 집합으로 만든다.
    2. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다
       • 퀵 정렬을 사용한다면 시간 복잡도는 $O(nlogn)$이며, 간선이 n이므로 $O(ElogE)$
    3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.
       • 최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것!
       • union-by-rank와 path compression 기법 사용 시 시간 복잡도가 결국 상수값에 가까움, $O(1)$

 

프림 알고리즘(Prim's algorithm)

시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 비용으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 비용 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해 가는 방식

 

1. 임의의 정점을 선택하여, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 비용을 가지는 간선부터 추출해서
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어있다면, 사이클을 막기 위해 스킵함
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에서 더 이상의 간선이 없을 때까지 3~4번을 반복

 

✨ 시간 복잡도

• 최악의 경우, while 구문에서 모든 간선에 대해 반복하고, 최소 힙 구조를 사용하므로 $O(ElogE)$ 시간 복잡도를 가짐
• 개선된 프림 알고리즘(extract min, decrease key 로직 사용)도 있으나, 설명이 길어지므로 해당 글에서는 생략함

 

📌 예시 문제

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다!

원더랜드는 모든 도시를 서로 연결하면서, 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소 비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

 

입력 설명

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용인 C인 도로로 연결되어 있다는 의미이다.

 

출력 설명 

모든 도시를 연결하면서 드는 최소 비용을 출력한다.

 

입력 예제

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

 

출력 예제

196

 

구현 코드 (크루스칼  알고리즘)

import java.util.*;

class Edge implements Comparable<Edge> {
    private int n1;
    private int n2;
    private int cost;

    public Edge(int n1, int n2, int cost) {
        this.n1 = n1;
        this.n2 = n2;
        this.cost = cost;
    }

    public int getN1() {
        return n1;
    }

    public int getN2() {
        return n2;
    }

    public int getCost() {
        return cost;
    }

    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost; // 비용 기준 오름차순
    }
}

public class Main {
    static int numOfCities;
    static int numOfRoads;
    static ArrayList<Edge> graph;
    static int[] unf;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        numOfCities = scanner.nextInt();
        numOfRoads = scanner.nextInt();
        graph = new ArrayList<>();

        // 연결 정보 입력받기
        for (int i = 0; i < numOfRoads; i++) {
            int n1 = scanner.nextInt();
            int n2 = scanner.nextInt();
            int cost = scanner.nextInt();
            graph.add(new Edge(n1, n2, cost));
        }

        // 집합 정보 확인할 배열 선언
        unf = new int[numOfCities + 1];
        for (int i = 1; i <= numOfCities; i++) {
            unf[i] = i; // 처음에는 다 다른 집합으로 적용
        }

        int answer = q.solution();
        System.out.print(answer);
    }

    private int solution() {
        int costSum = 0;

        // 비용이 작은 것 기준으로 정렬
        Collections.sort(graph);

        // 트리로 만들어 가면서, 최소 비용 구하기
        for (Edge e : graph) {
            int n1 = e.getN1();
            int n2 = e.getN2();
            int cost = e.getCost();

            if (find(n1) != find(n2)) {
                // 서로 다른 집합이므로, 트리를 만들 수 있다
                union(n1, n2);
                costSum += cost;
            }
        }

        return costSum;
    }

    // 집합 찾기
    private static int find(int n) {
        if (n == unf[n]) {
            return unf[n];
        } else {
            return unf[n] = find(unf[n]);
        }
    }

    // 집합으로 만들기
    private static void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) {
            unf[fa] = fb;
        }
    }
}

 

구현 코드 (프림 알고리즘)

import java.util.*;

class Edge implements Comparable<Edge> {
    private int nodeNum;
    private int cost;

    public Edge(int nodeNum, int cost) {
        this.nodeNum = nodeNum;
        this.cost = cost;
    }

    public int getNodeNum() {
        return nodeNum;
    }

    public void setNodeNum(int nodeNum) {
        this.nodeNum = nodeNum;
    }

    public int getCost() {
        return cost;
    }

    public void setCost(int cost) {
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }
}

public class Main {
    static int numOfCities;
    static int numOfRoads;
    static int[] check;
    static ArrayList<ArrayList<Edge>> graph;

    public static void main(String[] args) {
        Main q = new Main();

        Scanner scanner = new Scanner(System.in);
        numOfCities = scanner.nextInt();
        numOfRoads = scanner.nextInt();
        check = new int[numOfCities + 1];
        graph = new ArrayList<>();
        for (int i = 0; i <= numOfCities; i++) {
            graph.add(new ArrayList<>());
        }

        // 연결 정보를 입력받는다
        for (int i = 0; i < numOfRoads; i++) {
            // 무방향 인접 리스트로 저장한다
            int n1 = scanner.nextInt();
            int n2 = scanner.nextInt();
            int cost = scanner.nextInt();
            graph.get(n1).add(new Edge(n2, cost));
            graph.get(n2).add(new Edge(n1, cost));
        }

        // 우선순위큐를 사용해서 처리한다
        int answer = q.solution();
        System.out.print(answer);
    }

    private int solution() {
        int costSum = 0;

        // 가장 처음은 임의의 정점을 넣는다
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1, 0));
        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            int nowN1 = now.getNodeNum();
            int cost = now.getCost();
            if (check[nowN1] == 0) {
                check[nowN1] = 1; // 트리에 포함됨을 표시
                costSum += cost;
                for (Edge next : graph.get(nowN1)) {
                    if (check[next.getNodeNum()] == 0) {
                        pq.offer(new Edge(next.getNodeNum(), next.getCost()));
                    }
                }
            }
        }

        return costSum;
    }
}