본문으로 바로가기


MST(MCST, Minimum Cost Spanning Tree, 최소비용신장트리)는 약어 그대로 그래프에 존재하는 여러 개의 Spanning Tree 중 최소 비용을 가지는 것을 찾는 문제이다. 주로 간선(Edge)의 방향성이 없는 undirected graph에서 모든 Vertex(Node) 들을 방문하는 최소의 비용을 구하는 문제가 해당된다.

MST 문제를 해결하기 위한 알고리즘은 물론 여러 가지가 있을 수 있지만, 대표적으로 Kruskal's Algorithm(크루스칼 알고리즘)과 Prim Algorithm이 있다. Kruskal's Algorithm은 Merge Sort와 Union-Find를 사용하여 구현하는 알고리즘이고, Prim Algorithm은 Heap을 사용하여 구현하는 알고리즘이다.


알고리즘 문제들은 자신이 알고 있는 것이라고 해도 조건 단 하나가 추가되거나 빠지는 것 만으로도 전혀 다른 접근이 필요한 문제로 바뀔 수 있다. 때문에 한 가지 문제를 해결하기 위해서라도 연습할 때에는 다양한 종류의 알고리즘 기법을 적용하여 풀어보는 것이 좋을 것이다. 먼저 이번에는 Minimum Spanning Tree, MST를 풀기 위한 알고리즘 중 가장 대표적인 Kruskal's Algorithm에 대해 알아보고 관련 문제 한 개를 풀어보도록 하겠다.



Spanning Tree(신장 트리)란 무엇인가


Spanning Tree는 연결 그래프 부분 그래프 중 하나이다. 그래프의 모든 정점(Vertex)와 간선(Edge)의 부분 집합으로 구성되는 트리를 의미한다. 이 때 모든 노드는 적어도 하나의 간선에 연결 되어 있어야 한다. 쉽게 표현하자면 전체 연결 그래프 중에서 모든 정점을 포함하고, 정점들 끼리 간선을 통해 서로 연결되면서 사이클이 존재하지 않는 그래프이다. 아래 그림을 참고하자.




y노드를 연결 하는데 이미 두 개의 노드가 같은 Connected component에 속해 있다면 사이클이 생겼다는 것을 알 수 있다.


이를 다시한번 정리해 보면 아래 로직으로 코드를 구현할 수 있다.

1. 정점과 정점을 연결하는 간선에 대한 정보를 저장한다.

2. 1번의 정보를 간선의 가중치에 대한 오름차순 순으로 정렬한다.

3. Parent 배열을 정점의 수 만큼의 크기로 준비한 뒤, 각 정점들의 Parent를 자기 자신으로 할당한다.

3. Union-Find에서 Find를 위한 함수를 준비한다. 즉, 해당 노드가 속한 Connected component의 Root 노드를 반환하는 함수를 코딩한다.

4. 수행 속도를 향상시키기 위해 모든 자손들의 부모를 Root 정점으로 변경해주는 Path-Compression을 수행하여 대표 노드를 만든다.(Union-Find 기법)

5. 새로 연결하는 x의 Root와 y의 Root를 비교해 같지 않위와 같은 연결 그래프에서 a와 b는 모든 정점들이 간선을 통해 연결되어 있으며, 사이클이 존재하지 않는 Spanning Tree이다. 이에 비해 모든 정점들이 연결되어 있긴 하지만 정점 '1-2-3' 사이의 사이클이 존재하는 c와 정점2가 연결되어 있지 않은 d는 Spanning Tree가 아니다.

MST에서 우리의 목표는 이 여러 개의 Spanning Tree 중 최소 비용을 가지는 것을 구하는 것이다.


Kruskal Algorithm


Kruscal's Algorithm은 Greedy Algorithm의 대표적인 예이다. 크루스칼 알고리즘의 기본적인 아이디어는 아래와 같다.

1. 가장 Cost가 작은 것부터 추가하기 위해 간선의 정보를 가중치(Cost)에 대한 오름차순으로 정렬한다.

2. 가장 가중치가 작은 것부터 추가하며 사이클이 생기면 가장 높은 가중치부터 뺀다. '1번'의 결과로 가장 마지막에 넣은 간선이 가장 비싼 가중치를 가지므로 애초에 추가하지 않고 다음 단계를 진행하면 된다. '2번'을 수행하는 과정에서 사이클이 생겼는지를 체크하는 것은 DFS를 통해 가능하다. 하지만 DFS는 하나씩 모든 노드에 대해 다시 체크를 해야 하기 때문에 속도가 느리다. 빠른 속도로 사이클 존재여부를 체크 하기 위해서 Union-Find를 사용해 체크한다.


Union and Find 알고리즘의 기본 개념은 일단 모든 노드들의 대표 노드를 자기 자신으로 한 뒤, 노드들을 합칠 때 대표 노드를 정해 연결하는 것이다. 그렇게 되면 Find를 할 때, 대표 노드를 찾으면 해당 노드가 어떤 집합에 속해 있는지를 알 수 있게 된다. Union and Find 알고리즘에 대한 자세한 내용은 따로 별도의 포스팅을 통해 설명하도록 하겠다.

정렬된 노드들을 Union-Find를 통해 하나씩 합치다가 x노드와 으면 둘을 연결하고, 같으면 패스하는 로직을 구현한다.



고속도로 건설 문제


원리와 구현 로직에 대해 설명했지만 글로만 읽으면 잘 이해도 가지 않고 기억에도 남지 않기 때문에 예제 문제 한개를 Java 로 코딩해서 구현하며 연습해 보았다. 해당 문제는 고속도로 문제이다.


S 왕국의 새로운 정부는 모든 도시를 잇는 고속도로를 건설하려 한다.

(....중략.....) 

도로 후보의 목록이 주어질 때, 정부를 도와 모든 도시 간을 잇는 고속도로를 건설하는 최소 비용을 알아내자.


위와 같은 문제인데, 문제에 대한 전문은 http://koitp.org/problem/SDS_PRO_10_4/read/ 에서 확인해 볼 수 있다.

문제를 읽어 보면 모든 도시(정점)을 잇는 도로(간선) 을 만드는 최소 비용을 구하는 문제이다. 모든 정점을 연결하기 위한 최소의 비용은 각 도로를 사이클 없이 단 한번씩 연결하는 방법으로 구할 수 있다. 즉, Spanning Tree 중 최소 비용을 구하는 MST 문제이다. 

이 문제는 아래와 같은 Java 코드로 구현할 수 있으며, 간단한 주석을 달아 놓았으니 쉽게 읽을 수 있을 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//MST(MCST, Minimum Cost Spanning Tree)
public class ExpressWay {
    static int N;
    static int M;
    static int[] parent;
    static BufferedReader br;
    static StringTokenizer st;
    static Edge[] edges;
    static int minCost = 0;
     
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
         
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
         
        edges = new Edge[M];
        parent = new int[N+1];
         
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
         
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            edges[i] = new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        br.close();
         
        //주어진 간선들을 비용에 대한 오른차순으로 정렬
        Arrays.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge a, Edge b) {
                return a.cost - b.cost;
            }
        });
         
        for (int i = 0; i < M; i++) {
             
            int rootX = findRoot(edges[i].x);
            int rootY = findRoot(edges[i].y);
             
            if(rootX == rootY){
                continue;
            }else{
                /*Union-Find의 Union
                두개 Node를 연결. 즉 X의 Root 노드를 Y의 Root노드로 변경*/
                parent[rootX] = rootY;
                minCost = minCost + edges[i].cost;
            }
            
        }
        
        System.out.println(minCost);
 
    }
    
    //Union-Find 정점 x의 대표 node 찾기
    private static int findRoot(int x){
        if(x == parent[x]) {
            return x;
        }else{
            parent[x] = findRoot(parent[x]);
            return parent[x];
        }
         
    }
     
    private static class Edge{
        int x; 
        int y;
        int cost;
        public Edge(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
 
}
cs


 Other Contents 

댓글을 달아 주세요

  1. disable 2018.06.10 22:31 신고

    혹시 이 다리건설 문제를 씨로 구현하면 어떻게 표현이 되나요?

티스토리 툴바