[APS응용] 그래프최소비용1

 

[1] 상호배타집합

• 서로소 집합 : 중복 포함된 원소가 없는 집합 -> 교집합이 없다!
• 각 집합은 대표자를 통해 구분하며 연결리스트 또는 트리로 표현함
• 연결리스트
  • 같은 집합의 원소들은 하나로 연결된 리스트로 관리
  • 연결리스트의 맨 앞 원소를 집합 대표자 설정
  • 각 원소는 집합 대표 원소 가리키는 링크 가짐
• 트리
  • 하나의 집합 하나의 트리로 표현
  • 자식 노드는 부모 노드를 가리키며 루트 노드의 대표자

Make-Set(x)
	p[x] <- x
   
Find-Set(x)
	If x == p[x] : return x
    ELSE : return FIND-Set(p[x])
    
Union(x,y)
	p[Find-Set(y)] <- Find-Set(x)

 

 

🎨 [A] (Make-Set (1)~6) : 상호 배타 집합 초기 상태

💡 각 원소는 자기 자신을 대표자로 가리키고 있음 → p[x] = x (Make-Set 상태)

INDEX	1	2	3	4	5	6
P	1	2	3	4	5	6

 

🎨 [B] Union 연산 수행 후: 상호 배타 집합 변화 상태

💡 현재 상태 설명

• Union(1, 3) → 3이 1을 가리킴
• Union(2, 3) → 2가 Find-Set(3)=1을 가리킴 → 결국 2도 1을 가리킴
• Union(5, 6) → 6이 5를 가리킴

Make-Set(1) ~ Make-Set(6)
Union(1, 3)
Union(2, 3)
Union(5, 6)
Find-Set(6)

 

📊 P 배열 (부모 테이블)

INDEX	1	2	3	4	5	6
P	1	1	1	4	5	5

 

 

🎨 [C] Find-Set의 비효율적인 경우 (💣 성능 문제)

💡 문제 상황 설명

• 다음과 같은 구조로 집합이 연결되어 있음:
  a → b → c → d → e → f
• Find-Set(b)를 수행할 경우, 최종 대표자인 a를 찾기 위해
  b → c → d → e → f → a
  순서대로 여러 번 재귀 호출이 발생한다.

💡 구조 설명

Find-Set(b)

b → c → d → e → f → a

• 각 원소는 다음 원소를 부모로 가리키고 있음
• 루트 노드까지 가는 거리가 길수록 재귀 호출이 깊어지고 느려짐
• 이 구조는 선형 구조로, 최악의 경우 O(n)의 시간 복잡도가 발생함

💡 어떤 문제가 있는가?

• 비효율적인 탐색: 대표 원소를 찾기 위해 너무 많은 노드를 거쳐야 함
• 성능 저하: 연산이 쌓이면 전체 알고리즘 성능을 심각하게 떨어뜨릴 수 있음
• 특히 여러 번 Union을 수행한 이후 Find-Set의 성능이 급격히 나빠짐

 

🎨 [D] Rank를 이용한 Union (두 대표자의 Rank가 다를 경우)

💡 핵심 개념

• Rank는 트리의 깊이를 추정하는 값이다.
• Union 연산 시 두 집합의 **대표자(rank)**를 비교해서
  작은 쪽을 큰 쪽에 붙인다.
• 이렇게 하면 트리의 깊이를 최소화해서 Find-Set이 빠르게 작동한다!

집합 A

        [a, rank=2]
       /     \
  [b,1]     [d,1]
   /
[c,0]

집합 B

        [e, rank=1]
       /     \
  [f,0]     [g,0]

 

💡Union(A, B) 수행 시

• 대표자 a(rank=2), e(rank=1)
  → e 트리를 a 밑에 붙임
  → 더 rank가 낮은 e가 더 높은 a 밑으로 연결됨

💡왜 이렇게 하는가?

• 트리 깊이를 최소화해서
  Find-Set의 재귀 깊이/시간 복잡도 줄이기 위해서!
• 경로 압축과 함께 쓰면 성능 극대화!

💡결과 요약

• e 집합이 a 집합에 흡수됨
• 새로운 루트는 a, 깊이는 변화 없음 (rank 높은 쪽이 그대로 유지됨)
• Find-Set 효율성이 높아짐

 

🎨 [E] Path Compression (경로 압축)

💡 개념 요약

• Find-Set(x) 연산 중, x에서 루트까지 거쳐가는 중간 노드들 전부를 루트로 연결
• 이렇게 하면 트리의 높이가 줄어들고 이후 연산의 속도가 폭발적으로 향상된다!

Find-Set(h) 수행 전후 변화

상태 구조

🔹 Before	h → i → j → d → a
🔹 After	h → ai → aj → a

 

💡 시각적 비교

왼쪽: Find-Set(h) 호출 전 (트리 깊이가 깊음)
오른쪽: 호출 후 → e, h가 직접 a를 가리킴

Before:

h → i → j → d → a
           ↑
     (g, f도 d 밑에)

After:

h → a
e → a
(j, i도 a로 바로 연결됨)

 

💡 핵심 이점

• 한 번의 Find-Set 연산으로 전체 트리 납작하게
• 이후의 Find-Set은 거의 O(1)에 가까운 속도로 작동
• Disjoint Set의 성능을 좌우하는 필살기!!

 

[2] 최소 비용 신장 트리 (Minimum spanning tree)

신장 트리 : 그래프의 모든 정점과 간선의 부분집합으로 구성되는 트리
                   간선의 개수는 무조건 N-1개가 될 수 밖에 없다!

 

 

최소 신장 트리

• 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리
• 무 방향 가중치 그래프
• N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용
• 사이클을 포함하지 X
• 사용하는 이유
  • 도로망, 통신망, 유통망 등 여러 분야에서 비용을 최소로 해야 이익을 볼 수 있음
  • 대표적인 알고리즘으로 크루스칼, 프림이 있음

 

 

[3] KRUSKAL algorithm

크루스칼 알고리즘

• 대표적인 그리디 알고리즘 중 하나임
• 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
• 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 -> 사이클이 존재하면(unionFind) 다음으로 가중치가 낮은 간선 선택
• N-1개의 간선이 선택될 때까지 반복

 

MST-KRUSKAL(G)
	A <- 0
    FOR v in G.V
    	Make-Set(v)
    G.E에 포함된 간선들을 가중치 w에 의해 정렬
    FOR 가중치가 가장 낮은 간선 (u,v) 에 포함 된 G.E 선택 (n-1개)
    	IF Find-Set(u) != Find-Set(v)
        	A <- A U ((u,v))
            Union(u,v)
    RETURN A

 

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

// 크루스칼 알고리즘으로 최소 신장 트리(MST)를 구하는 예제
public class 그래프최소비용01_크루스칼 {

    static int[] p; // 각 노드의 대표(부모)를 저장하는 배열 (Disjoint Set용)

    // 간선 정보를 저장할 클래스 정의
    static class Edge implements Comparable<Edge> {
        int s, e, cost;

        public Edge(int s, int e, int cost) {
            this.s = s;         // 시작 노드
            this.e = e;         // 끝 노드
            this.cost = cost;   // 간선 가중치
        }

        // 디버깅용 출력 포맷
        @Override
        public String toString() {
            return "Edge [s=" + s + ", e=" + e + ", cost=" + cost + "]";
        }

        // 간선을 가중치 기준으로 오름차순 정렬
        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt(); // 정점 수
        int E = sc.nextInt(); // 간선 수

        Edge[] edges = new Edge[E]; // 간선 배열

        // 간선 정보 입력
        for (int i = 0; i < E; i++) {
            int s = sc.nextInt();       // 시작 정점
            int e = sc.nextInt();       // 끝 정점
            int cost = sc.nextInt();    // 가중치
            edges[i] = new Edge(s, e, cost);
        }

        // 1. 간선을 가중치 기준으로 오름차순 정렬
        Arrays.sort(edges);

        // 2. 서로소 집합(Union-Find) 초기화
        p = new int[V];
        for (int i = 0; i < V; i++) {
            p[i] = i; // 자기 자신을 대표로 초기화
        }

        int ans = 0;     // 최종 최소 비용 누적 값
        int pick = 0;    // 선택한 간선 수 (MST는 V-1개의 간선을 선택해야 함)

        // 3. 간선을 하나씩 확인하면서 MST 만들기
        for (int i = 0; i < E && pick < V - 1; i++) {
            int px = findSet(edges[i].s); // 간선의 시작점의 대표 노드
            int py = findSet(edges[i].e); // 간선의 끝점의 대표 노드

            // 대표 노드가 다르면 사이클이 발생하지 않음 -> 간선 선택
            if (px != py) {
                union(px, py);                 // 두 노드를 하나의 집합으로 합치기
                ans += edges[i].cost;          // 가중치 누적
                pick++;                        // 간선 선택 개수 증가
            }
        }

        // 4. 최소 비용 출력
        System.out.println(ans);
    }

    // findSet: 대표 노드를 찾는 함수 (경로 압축 기법 사용)
    static int findSet(int x) {
        if (x != p[x]) {
            p[x] = findSet(p[x]); // 부모를 따라 재귀적으로 찾아가며 경로 압축
        }
        return p[x];
    }

    // union: 두 집합을 합치는 함수
    static void union(int x, int y) {
        p[y] = x; // 단순히 y를 x 밑으로 붙이기 (랭크 고려 안 함)
    }
}