P.1197 최소 스패닝 트리

코드

1. 크루스칼 알고리즘

import java.io.*;
import java.util.*;

public class Main {

    static int v, e;
    static ArrayList<Node> graph;
    static int[] parent;

    static public class Node {
        int edge1, edge2;
        int weigh;

        public Node(int edge1, int edge2, int weigh) {
            this.edge1 = edge1;
            this.edge2 = edge2;
            this.weigh = weigh;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        v = line[0]; e = line[1];
        graph = new ArrayList<>();
        for (int i = 0; i < e; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            graph.add(new Node(line[0], line[1], line[2]));
        }
        Collections.sort(graph, Comparator.comparing(o -> o.weigh));

        parent = new int[v + 1];
        for (int i = 1; i <= v; i++) parent[i] = i;
        bw.write(Integer.toString(kruskal()));
        bw.flush();

        bw.close();
        br.close();
    }

    private static int kruskal() {
        int weigh = 0;
        for (Node node : graph) {
            if (!isSameParent(node.edge1, node.edge2)) {
                union(node.edge1, node.edge2);
                weigh += node.weigh;
            }
        }

        return weigh;
    }

    private static void union(int edge1, int edge2) {
        edge1 = find(edge1);
        edge2 = find(edge2);

        if (edge1 != edge2) parent[edge2] = edge1;
    }

    private static boolean isSameParent(int edge1, int edge2) {
        if (find(edge1) == find(edge2)) return true;

        return false;
    }

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

        return find(parent[edge]);
    }
}

2. 프림 알고리즘

package Baekjoon.Class;

import java.io.*;
import java.util.*;

public class P_1197 {

    static int v, e;
    static ArrayList<Edge>[] graph;
    static int ans = 0;

    static public class Edge {
        int end;
        int weigh;

        public Edge(int end, int weigh) {
            this.end = end;
            this.weigh = weigh;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        v = line[0]; e = line[1];
        graph = new ArrayList[v + 1];
        for (int i = 0; i <= v; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < e; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            graph[line[0]].add(new Edge(line[1], line[2]));
            graph[line[1]].add(new Edge(line[0], line[2]));
        }

        prim(1);

        bw.write(Integer.toString(ans));
        bw.flush();
    }

    private static void prim(int start) {
        PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparing(o -> o.weigh));
        queue.add(new Edge(start, 0));
        boolean[] visited = new boolean[v + 1];

        while (!queue.isEmpty()) {
            Edge poll = queue.poll();

            if (!visited[poll.end]) {
                visited[poll.end] = true;
                ans += poll.weigh;

                for (Edge edge : graph[poll.end]) {
                    if (!visited[edge.end]) {
                        queue.add(edge);
                    }
                }
            }
        }
    }
}

코드 설명

최소신장트리(MST)에는 두 가지 알고리즘이 있다.

1. 크루스칼 알고리즘
2. 프림 알고리즘

 

크루스칼은 간선 중심의 알고리즘이고 시간복잡도가 O(ElogE)이기 때문에 간선이 정점의 수보다 적을 때 사용하는 것이 좋다.

프림은 정점 중심의 알고리즘이고 시간복잡도가 O(ElogV)이기 때문에 정점이 간선의 수보다 적을 때 사용하는 것이 좋다.

크루스칼 알고리즘이 O(ElogV)로 알려져 있는 경우가 많은데 이는 크루스칼 루프 자체의 값이지 실제 코드에서는 정렬하는 과정이 필요하기 때문에 O(ElogE)가 맞다.

 

1. 크루스칼 알고리즘

크루스칼 알고리즘은 다음의 과정을 거친다.

1. 간선을 오름차순으로 정렬
2. Union - Find

Step1. 간선을 오름차순으로 정렬

: O(E * logE)

 

Step2. Union-Find

: O(E * logV)

크루스칼 알고리즘 루프(O(E))에 들어가게 되면 Union-Find(O(logV))가 반복적으로 일어난다.

 

Union-Find에서 핵심은 parent 배열이다.

parent 배열은 서브트리의 루트이다.

만약 다음과 같은 입력이 있다고 가정하자.

4 5
1 2 5
2 3 2
3 4 3
1 4 4
2 4 -4

제일 먼저 연결되는 두 정점은 2-4다.

두 정점과 하나의 간선이 존재하므로 2와 4는 하나의 서브트리를 이룬다.

이 때 parent[4] = 2다.

4의 루트가 2이기 때문이다.

 

다음으로 연결되는 두 정점은 2-3이다.

두 정점과 하나의 간선이 존재하므로 2와 3도 하나의 서브트리를 이룬다.

이 때 Parent[3] = 2이다.

 

다음으로 연결 시도되는 두 정점은 3과 4이다.

parent[3] = parent[4] = 2이므로 현재 두 정점은 각각 2를 루트로 하는 서브트리에 속해있다.

만약, 3과 4를 연결하게 되면 위 서브트리는 순환구조가 되어버린다.

 

즉, parent배열은 순환을 막아주는 역할을 한다.

또한 크루스칼 알고리즘에서 연결되는 각 정점은 모두 하나의 서브트리라고 본다면 이해가 쉬워진다.

 

 

그럼 다시, Find함수와 Union함수가 무슨 역할을 하는지 알아보자.

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

    return find(parent[edge]);
}

find함수는 해당 정점이 속해있는 서브트리의 루트를 찾는 역할을 한다.

 

private static void union(int edge1, int edge2) {
    edge1 = find(edge1);
    edge2 = find(edge2);

    if (edge1 != edge2) parent[edge2] = edge1;
}

Union함수는 해당 정점이 속해있는 서브트리의 루트로 parent 배열을 업데이트 해 주는 역할을 한다.

 

2. 프림 알고리즘

프림 알고리즘 자체는 bfs 느낌이 강하다.

 

크루스칼 알고리즘에 비해 PriorityQueue를 쓰면 상황 종료되는 느낌이다.

모든 정점에 대해서 돌려 볼 필요도 없는 게 무조건 한 정점을 지나고 그 정점에서 뻗어나오는 간선들 중 하나의 간선으로 MST를 구성할 것이기 때문에 한 정점에 대해서 시작지점을 정하고 한 번만 돌려보면 된다.

 

queue는 모든 간선에 대한 정보를 확인할 것이고 (O(E)) 중첩 반복문은 본인과 연결된 정점의 개수에 대해서 확인을 하지만 PriorityQueue이기 때문에 O(logV)의 시간복잡도를 가지게 된다.

그렇기 때문에 프림 알고리즘의 시간복잡도는 O(E * logV)가 되는 것이다.

 

 

개인적으로 프림 알고리즘은 친숙하고 초반에 생각한 아이디어와 유사한데 크루스칼 알고리즘은 좀 생소했다.

아마 지금까지 알고리즘 문제를 풀면서 트리가 나오던지 그래프가 나오던지 모두 그래프로 풀었던 탓인 것 같다.

왜냐면 트리는 그래프의 한 종류이기 때문에..

하지만 그래프는 트리가 아니다. 그래서 크루스칼 알고리즘을 공부하면서 '루트'라는 개념이 되게 생소하게 느껴졌다.

크루스칼 알고리즘에서 많이 배웠던 것은 루트를 배열로 저장하고 사용하면 굉장히 편리하다는 점이다.