[BOJ / 백준] 백준 1197 최소 스패닝 트리 - (자바 / JAVA)

백준 1197 최소 스패닝 트리 - JAVA (자바) 

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

1197번: 최소 스패닝 트리

---

문제

그래프와 최소 스패닝 트리

 

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

예제 입력 :

3 3
1 2 1
2 3 2
1 3 3

 

예제 출력 :

3

---

최소 스패닝 트리 (Minimum Spanning Tree)

스패닝 트리(Spanning Tree)는 모든 정점을 포함하면서, 순환이 없는 그래프입니다.

모든 정점을 포함하고 최소한의 간선을 사용해서 그래프를 연결하는 트리 구조를 말합니다.

정점의 개수가 N개라면 스패닝 트리의 간선은 N-1개입니다.

스패닝 트리는 하나의 그래프에서 여러 개의 스패닝 트리가 존재할 수 있습니다.

 

최소 스패닝 트리(Minimum Spanning Tree)는 스패닝 트리 중에서

간선의 가중치의 합이 최소가 되는 스패닝 트리를 말합니다.

최소 스패닝 트리를 구하는 알고리즘으로는

- 크루스칼(Kruskal) 알고리즘 

- 프림 (Prim) 알고리즘 

이 있습니다.

---

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 간선을 중심으로 계산하는 알고리즘입니다.

그래프에서 간선의 가중치가 작은 간선부터 순서대로 선택해서

간선에 연결된 부모 정점을 확인하고 간선을 추가해 나가는 방식입니다.

 

간선의 정보가 들어있는 Node를 우선순위 큐를 사용해서 가중치가 작은 순서로 정렬한 뒤

각 간선에 연결된 정점의 부모 정점을 확인하고 부모가 같지 않으면 사이클이 발생하지 않는 간선이기 때문에

간선을 추가하는 방식으로 코드를 작성했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 최소스패닝트리_KruskalMST {
    private static int V, E;
    private static PriorityQueue<Node> pq;
    private static int[] parent;

    private static class Node {
        int nextNode;
        int prevNode;
        int cost;

        Node(int nextNode,int prevNode, int cost) {
            this.nextNode = nextNode;
            this.prevNode = prevNode;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

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

        pq = new PriorityQueue<>((o1, o2) -> {
            return Integer.compare(o1.cost, o2.cost);});
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            pq.add(new Node(start, end, cost));
        }

        int size = pq.size();
        int result = 0;
        for (int i = 0; i < size; i++) {
            Node now = pq.poll();
            int x = find(now.nextNode);
            int y = find(now.prevNode);

            if (!isSameParent(x, y)) {
                result += now.cost;
                union(x, y);
            }
        }

        System.out.println(result);
    }

    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    private static void union(int x, int y) {
        if (find(x) != find(y)) {
            parent[y] = x;
        }
    }

    private static boolean isSameParent(int x, int y) {
        if (find(x) == find(y)) {
            return true;
        } else {
            return false;
        }
    }
}

 

---

프림(Prim) 알고리즘

프림 알고리즘은 정점을 중심으로 계산하는 알고리즘입니다.

시작 정점에서 출발해서 연결된 간선 중 가중치가 작은 간선을 차례대로 연결해가는 방식입니다.

 

인접 리스트를 사용하여 그래프를 저장한 뒤 우선순위 큐를 사용하여방문하지 않은 정점일 경우 방문처리를 하고 가중치의 값을 더해가면서 가중치의 합을 계산했습니다.프림 알고리즘은 방문하지 않은 정점으로만 간선을 연결하기 때문에 사이클 검사를 하지 않습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 최소스패닝트리_PrimMST {
    private static int V, E;
    private static ArrayList<Node>[] adjList;
    private static boolean[] visited;

    private static class Node {
        int nextNode;
        int cost;

        Node(int nextNode, int cost) {
            this.nextNode = nextNode;
            this.cost = cost;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        visited = new boolean[V + 1];
        adjList = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            adjList[start].add(new Node(end, cost));
            adjList[end].add(new Node(start, cost));
        }

        System.out.println(countWeight(1));
    }

    private static int countWeight(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            return Integer.compare(o1.cost, o2.cost);}
        );
        pq.add(new Node(start, 0));
        int cost = 0;

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (visited[now.nextNode]) {
                continue;
            }

            visited[now.nextNode] = true;
            cost += now.cost;

            for (Node next : adjList[now.nextNode]) {
                if (!visited[next.nextNode]) {
                    pq.add(next);
                }
            }
        }

        return cost;
    }
}

---

실행시간 비교

백준 1197번 최소 스패닝 트리 실행 시간 비교

 

간선이 많은 밀집 그래프의 경우 정점을 중심으로 계산하는 프림 알고리즘이 더 효율적이고간선이 적은 희소 그래프의 경우 크루스칼 알고리즘이 더 효율적입니다.