백준 1197 최소 스패닝 트리 - JAVA

1197 문제 링크

---

https://www.acmicpc.net/problem/1197

 

문제 설명

---

 

입출력

---

 

코드

---

<프림 알고리즘>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static boolean[] visit;
    static List<int[]>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        visit = new boolean[N+1];
        list = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        } 
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list[a].add(new int[] {b, c});
            list[b].add(new int[] {a, c});
        }
        bw.write(String.valueOf(primSpanning()));
        bw.flush();
    }
    private static int primSpanning() {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
        pq.offer(new int[] {1, 0});
        int total = 0;
        while(!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentNode = (int) current[0];
            int currentWeight = current[1];
            if (!visit[currentNode]) {
                visit[currentNode] = true;
                total += currentWeight;
                for (int[] next : list[(int) current[0]]) {
                    int nextNode = (int) next[0];
                    int nextWeight = next[1];
                    if(!visit[nextNode]) {
                        pq.offer(new int[] {nextNode, nextWeight});
                    }
                }
            } 
        }
        return total;
    }
}

 

<크루스칼 알고리즘>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int parent[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        parent = new int[N+1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        } 
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            pq.add(new int[] {a, b, c});
        }
        int total = 0;
        for (int i = 0; i < M; i++) {
            int[] current = pq.poll();
            int start = find(current[0]);
            int end = find(current[1]);
            if (!isSameParent(start, end)) {
                total += current[2];
                union(current[0], current[1]);
            } 
        } 
        bw.write(String.valueOf(total));
        bw.flush();
    }
    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[y] = x;  
        } 
    }
    private static int find(int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]); 
    }
    private static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return true;
        } else {
            return false;
        }
    }
}

 

알고리즘 설명

---

최소 스패닝 트리의 '스패닝'은 번역하면 '신장'으로 최소 신장 트리(MST)에 관해 알고있는지를 묻고있는 문제입니다. 최소 신장 트리란 그래프의 모든 정점을 포함하면서 사이클이 없고, 각 간선의 비용의 합이 최소로 연결된 트리를 말하는 것입니다. 최소 신장 트리를 찾는 알고리즘은 크게 두 가지가 있습니다. 바로 프림 알고리즘과 크루스칼 알고리즘입니다.

 

프림 알고리즘은 최소 힙과 Priority Queue를 활용한 알고리즘으로, 동작 방식은 N개의 노드 중 임의로 하나를 선택한 후, 해당 노드와 연결된 간선들 중에서 아직 방문하지 않은 노드로 가는 최소 비용 간선을 선택합니다. 그런 다음, 새롭게 연결된 노드와 기존에 연결된 노드들 사이에서 가장 가중치가 작은 간선을 선택하여 계속해서 트리를 확장해 나갑니다. 이 과정에서 사이클을 방지하려면, 이미 방문한 노드를 다시 선택하지 않도록 해야 합니다. 즉, 연결하려는 간선의 다른 끝점이 이미 방문된 노드라면, 해당 간선은 선택하지 않고 아직 방문하지 않은 노드로 가는 간선을 선택합니다. 이 과정을 간선의 개수가 N-1개가 될 때까지 반복하면, 모든 노드를 포함하면서 최소 비용으로 연결된 트리를 얻을 수 있습니다. 결과적으로 모든 노드를 포함하고 사이클 없이 최소 비용을 가지므로, 최소 신장 트리의 조건인 신장트리와 최소비용간선을 만족합니다.

프림 알고리즘에 대해 증명이나 더 깊게 알아보고 싶은 분들은 아래 위키백과 링크 참고바랍니다.

 

프림 알고리즘 - 위키백과, 우리 모두의 백과사전

---

크루스칼 알고리즘은 UnionFind + PriorityQueue를 활용한 알고리즘으로, 동작방식은 간선을 오름차순으로 나열한 후, 가중치가 작은 순서대로 사이클 방지 작업을 거쳐 스패닝 트리에 추가합니다. 사이클 방지작업은 UnionFind알고리즘을 활용하여 진행됩니다. 먼저 선택된 간선의 정점의 대표 노드를 확인합니다. 이를 위해 find() 함수를 사용하여 각 정점이 속한 집합의 대표 노드를 찾습니다. 만약 두 정점의 부모가 같다면 이미 같은 트리(집합)에 속해 있기 때문에, 그 간선을 추가하면 사이클이 발생하게 됩니다. 따라서 이 경우 해당 간선을 건너뛰고, 두 정점이 다른 집합에 속한다면 union() 함수를 사용하여 두 집합을 하나로 합칩니다. 이 과정을 통해 간선을 추가할 때마다 사이클을 방지하게 됩니다. 크루스칼 알고리즘은 프림 알고리즘과 결과적으로는 동일하게 모든 노드를 포함하면서 사이클이 없고 최소 비용을 가지므로 최소 신장 트리의 조건인 신장트리 + 최소비용간선을 만족하게 됩니다.

크루스칼 알고리즘에 대해 증명이나 더 깊게 알아보고 싶은 분들은 아래 위키백과 링크 참고바랍니다.

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

 

두 알고리즘은 MST를 생성하는 방식에 차이가 있기 때문에 시간 복잡도에도 차이가 발생합니다. 프림 알고리즘은 노드를 기준으로 연결 과정을 반복하는 반면, 크루스칼 알고리즘은 간선을 기준으로 연결 과정을 반복합니다. 이로 인해 프림 알고리즘은 O(ElogV)의 시간 복잡도를 가지며, 크루스칼 알고리즘은 O(ElogE)의 시간 복잡도를 가집니다. E(간선)와 V(정점)의 수는 그래프의 특성에 따라 영향을 주기 때문에, 간선이 많은 그래프에서는 크루스칼 알고리즘이 더 효율적이고, 노드가 많고 간선이 적은 밀도가 낮은 그래프에서는 프림 알고리즘이 유리합니다.

 

두 알고리즘의 차이를 간단하게 표로 정리해보이겠습니다.

 

 

- 참고 -

• 트리의 기본조건 : 사이클 X, 루트 노드 존재, N개의 노드가 N-1개의 간선으로 연결

 

코드 해석

---

[ 프림 알고리즘 ]

정점과 간선을 입력받고 간선의 수 만큼 list 배열에 저장합니다. PriorityQueue로 가중치가 낮은 간선부터 처리합니다. 시작 노드를 1로 설정하고, 시작 노드에 연결된 간선들을 큐에 삽입합니다. 큐에서 가장 가중치가 낮은 간선을 선택하여 연결된 노드가 방문되지 않은 경우, visit 배열의 해당 노드 자리를 true로 바꾸고, 방문한 노드에서 연결된 새로운 간선들을 추가합니다. 이때, total 변수에 간선의 가중치 값을 더해줍니다. 즉, 새로운 간선을 선택할 때마다 그 간선의 가중치를 total에 추가하여 최소 비용을 계속 누적시킵니다. 모든 노드가 방문 처리될 때까지 해당 과정을 반복하며, 종료되면 total을 출력합니다.

 

[ 크루스칼 알고리즘 ]

정점과 간선을 입력받고, 간선들을 가중치 순으로 정렬한 뒤, PriorityQueue를 사용하여 가장 작은 간선부터 차례대로 처리합니다. isSameParent 함수를 이용해 간선의 양 끝점이 서로 다른 집합에 속하는지 확인하고, 다르다면 그 간선을 선택하여 total에 가중치를 더한 후, union 연산으로 두 노드를 하나의 집합으로 합칩니다. 만약 두 노드가 이미 같은 집합에 속한다면, 그 간선은 건너뛰고 다음 간선을 처리합니다. 이 과정을 반복하여 모든 간선이 처리되면 total을 출력합니다.