[Algorithm] 백준 유니온 파인드문제 - 최소 스패닝 트리(1197) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드 문제 - 최소 스패닝 트리 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = parseInt(st.nextToken());
        int e = parseInt(st.nextToken());
        
        Graph graph = new Graph(v); // 그래프 설정
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            graph.addEdge(parseInt(st.nextToken()), parseInt(st.nextToken()), parseInt(st.nextToken()));
        }
        
        System.out.println(graph.mst());
    }
}

class Graph {
    int n; // n개의 노드
    int[] parent; // 유니온 파인드 루트 노드
    List<Edge> edges = new ArrayList<>(); // 간선
    
    Graph(int n) {
        this.n = n;
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
    }
    
    class Edge {
        int x; // 연결된 노드
        int y; // 연결된 노드
        int w; // 가중치
        
        Edge (int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
    
    void addEdge(int x, int y, int w) {
        edges.add(new Edge(x, y, w));
    }
    
    int mst() {
        int result = 0;
        edges.sort(Comparator.comparing((Edge e) -> e.w)); // 엣지 오름차순 설정

        for (Edge e : edges) {
            int p1 = find(e.x); // x의 루트 노드
            int p2 = find(e.y); // y의 루트 노드

            if (p1 == p2) continue; // 만약 두 노드의 루트 노드가 같다면 패스
            result += e.w; // 가중치 업데이트
            union(p1, p2); // 두 노드 합치기
        }
        
        return result;
    }
    
    int find(int child) { // find 경로 압축
        if (child == parent[child]) return child;
        return parent[child] = find(parent[child]);
    }
    
    void union(int p1, int p2) { // union 합치기
        parent[p2] = p1;

    }
}

 

2. 최소 스패닝 트리(MST)

 

최소 스패닝 트리를 구하는 알고리즘은 Kruskal 알고리즘이 있습니다.

Kruskal 알고리즘은 다음의 순서로 진행됩니다.

• 그래프의 모든 간선을 가중치에 따라 오름차순 정렬합니다.
• 가중치가 최소인 간선을 선택하여, 간선의 두 노드가 같은 집합에 있지 않는 경우 (루트가 다른 경우) 해당 간선에 연결된 두 노드를 하나의 집합으로 합칩니다 (유니온 파인드)
• 만약 간선이 연결하는 두 노드가 같은 집합이라면 사이클이 형성될 수 있으므로 건너뜁니다.
• 모든 간선이 검사 될 때까지 과정을 반복합니다.

     

        7

1 ------------- 2

                    | 

                    |  10  

                    |

                    3 -------------- 4

                              5

 

다음과 같은 트리가 존재한다고 가정하겠습니다.

• Kruskal 알고리즘의 순서에 따라 가중치가 가장 적은 (3, 4) 엣지, (1, 2) 엣지, (2, 3) 엣지로 정렬합니다.
• (3, 4)에 있는 노드 3, 4의 루트 노드를 검사합니다. (아직 업데이트되지 않았기에 3의 루트 노드 3, 4의 루트 노드 4)
• 두 루트 노드가 다르므로 하나로 합칩니다. 저는 x1, x2가 있을 때, x1을 루트 노드로 설정하였습니다.
• 마찬가지로 (1, 2) 엣지를 선택하여 두 노드에 대한 유니온 파인드를 진행합니다.
• 다음 엣지인 (2, 3)을 선택하여 두 노드에 대한 유니온 파인드를 진행합니다.
• 이 과정에서 분리되어 있던 두 집합 {1, 2} , {3, 4}가 하나로 합쳐지게 됩니다.
• 모든 간선에 대한 탐색을 마쳤으므로 종료합니다.

만약 해당 그래프에서 

 

        7

1 ------------- 2

  \                  | 

   \                 |  10  

    \                |

     \------------ 3 -------------- 4

   100                      5

 

1과 3을 잇는 간선이 추가될 경우 사이클을 형성할 수 있습니다.

유니온 파인드에서 두 루트 노드가 같은 경우에는 건너뛰는 이유가 바로 이러한 사이클을 방지하기 위함입니다.

이미, 간선으로 오름차순 설정하였기 때문에 후에 오는 간선은 이전에 설정한 간선보다 더 작기 때문에
그리디한 탐색 방법이 MST에서는 최적의 해를 찾을 수 있는 것입니다.

 

int mst() {
    int result = 0;
    edges.sort(Comparator.comparing((Edge e) -> e.w)); // 엣지 오름차순 설정

    for (Edge e : edges) {
        int p1 = find(e.x); // x의 루트 노드
        int p2 = find(e.y); // y의 루트 노드

        if (p1 == p2) continue; // 만약 두 노드의 루트 노드가 같다면 패스
        result += e.w; // 가중치 업데이트
        union(p1, p2); // 두 노드 합치기
    }
    
    return result;
}

 

이러한 원리를 바탕으로 소스를 보면, 먼저 엣지의 가중치를 기준으로 정렬하고,

각 간선을 탐색합니다. 엣지에 대한 노드를 유니온 파인드를 진행하고 result에 가중치를 더해줍니다

나중에는 오름차순에 따라 간선이 나오게 되며 결국 분리되어 있는 여러 개의 집합이 하나로 합쳐지기 때문에 이러한 방법을 택할 수 있습니다.

 

이상으로 백준 최소 스패닝 트리 자바 풀이를 마치도록 하겠습니다. 감사합니다!