[C++/LeetCode] Min Cost to Connect All Points - using MST

Daily LeetCoding Challenge for April, Day 26.

문제

맨하튼 거리가 최소가 되도록 정점을 연결하고, 가중치의 최소 합을 구하기

아이디어: 최소 신장 트리 MST

---

최소 신장 트리 Minimum Spanning Tree, MST

 

Spanning Tree

그래프에서 모든 정점이 연결되도록 만든 그래프

즉 다음과 같이 모든 Edge들이 연결되지 않아도 된다. 즉 최소 연결 그래프

참조: https://en.wikipedia.org/wiki/Spanning_tree#Algorithms

 

Spanning Tree는 DFS, BFS에 의해 O(n) 으로 찾을 수 있으며, cycle을 생성해서는 안된다.

따라서 모든 node를 포함하기 때문에 정확하게 (n-1)개의 edge로 연결된다.

 

 

Minimum Spanning Tree

spanning tree를 생성할 때 Edge들의 가중치의 합이 최소가 되도록 구성한 tree.

이 MST를 구현하는 데는 크게 두가지 알고리즘이 있다.

 

1. Kruskal Algorithm

2. Prim Algorithm

 

이 중에서 내가 Prim으로 문제를 풀었기 때문에 Prim을 정리하도록 하겠다.

Prim Algorithm

 

동작 원리

 

1. 그래프에서 하나의 임의의 꼭짓점을 선택하여 트리를 만든다.
2. 그래프의 모든 변이 들어 있는 집합을 만든다.
3. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
    트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.

알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다.

 

 

즉 맨 처음에는 임의로 시작 node를 MST 집합에 포함한다. 그냥 {0, 0} 으로 많이 함.

그 다음 집합에 포함된 시작 node와 인접한 node들 중에서 가장 가중치가 낮은 edge를 선택하여 해당 Node를 집합에 포함한다.

이때 cycle이 생성되지 않도록 하기 위해서 node를 방문했는지 아닌지 확인하는 방법이 필요하다. 이를 다양하게 구현 가능한데, 대부분은 node의 개수만큼 vector<bool> visited   를 만들어서 방문시 true, 아닌 경우 false로 체크한다.

 

이 과정을 반복하는 것이다.

kruskal과 달리 tree를 단계적으로 확장해나가는 방법이다.

 

이때 MST 집합을 min heap으로 구현하면 가장 작은 가중치를 쉽게 구할 수 있기 때문에 편하다. c++에서는 priority queue로 min heap을 구현 가능하다.

---

완성

class Solution
{
public:
    int getDistance(vector<int> v1, vector<int> v2)
    {
        return abs(v1[0] - v2[0]) + abs(v1[1] - v2[1]);
    }
    int minCostConnectPoints(vector<vector<int>>& points)
    {
        int len = points.size();
        int sum = 0;
        int curNode, curDist;
        
        // MST 집합을 min heap으로 구현
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        // node를 방문했는지 아닌지 확인하는 용도
        vector<bool> visited(len);
        
        // 임의의 시작 노드: first - 가중치
       	//		second - 노드 index
        pq.push({0, 0});
        
        while (!pq.empty())
        {
            curNode = pq.top().second;	// node index
            curDist = pq.top().first;	// 가중치
            pq.pop();					// 집합에 포함했으니 삭제
            
            // 방문했던 노드라면 가중치 합에 추가하지 않음. 즉 연결하지 않음.
            if (visited[curNode] == true)
                continue;
                
            // 방문하지 않았다면 visited를 true로 만들어서 연결하고, 가중치 합에 추가함.
            else
            {
                visited[curNode] = true;
                sum += curDist;
            }
            // 새로 추가된 node와 연결된 미방문 간선들을 집합에 추가함
            for(int i = 0;i < len;i++)
                if (visited[i] == false)
                    pq.push({getDistance(points[curNode], points[i]), i});
        }
        
        return sum;
    }
    
};

 

참고 문헌 및 자료

https://en.wikipedia.org/wiki/Spanning_tree#Algorithms

Spanning tree - Wikipedia

https://ko.wikipedia.org/wiki/프림_알고리즘

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html