섬 연결하기

최소 신장 트리, C++

 

최소 신장 트리, MST(Minimum Spanning Tree) 알고리즘은 두 가지 방식으로 풀 수 있다.

크루스칼 알고리즘과 프림 알고리즘이다.

 

크루스칼 알고리즘은 간선을 가중치가 작은 순서대로 오름차순으로 정렬을하고,

사이클을 형성하지 않는 방향으로 간선을 선택하며 트리를 구성한다.

정점이 많을 때 효과적인 알고리즘이다.

 

프림 알고리즘은 아무 정점을 시작 정점으로 설정한 뒤, 시작 정점의 인접 정점들 중에 가장 가중치가 작은 간선을 선택하며 정점을 잇는다.

하나의 정점을 잇게 되면, 현재까지 방문한 정점들의 인접 정점중에서 방문하지 않으면서 가장 작은 가중치를 가진 간선을 선택하는 알고리즘이다.

이렇게 되면 문제는 정점이 많아지게 된다면, 이전 방문했던 모든 정점들의 인접 정점들을 조사해야하기 때문에 꽤나 복잡도가 커지게 된다.

때문에 정점이 많은 경우라면 크루스칼 알고리즘을 선택하고 풀면 될 것 같다.

 

- 크루스칼 알고리즘

// 크루스칼 알고리즘은 간선을 먼저 가중치가 작은 순서대로 오름차순으로 정렬을 하고,
// 사이클을 형성하지 않도록 간선을 선택하면 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int getRoot(vector<int>& parent, int x){
    if(parent[x] == x) return x;
    
    return parent[x] = getRoot(parent, parent[x]);
}

void unionParent(vector<int>& parent, int a, int b){
    a = getRoot(parent, a);
    b = getRoot(parent, b);
    
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

bool find(vector<int>& parent, int a, int b){
    a = getRoot(parent, a); // 루트 정점을 반환
    b = getRoot(parent, b);
    
    if(a == b) return true;
    else return false;
}

bool compare(vector<int> a, vector<int> b){
    return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    sort(costs.begin(), costs.end(), compare);
    
    vector<int> parents(n);
    
    for(int i = 0; i < parents.size(); ++i){
        parents[i] = i;
    }
    
    for(int i = 0; i < costs.size(); ++i){
        // 간선을 선택하고, 두 정점의 부모 정점을 찾음
        // 만약 부모 정점이 같으면 사이클을 형성하게 되므로
        // 부모 정점이 같지 않은 경우에만 하나의 그룹으로 형성
        if(!find(parents, costs[i][0], costs[i][1])){
            unionParent(parents, costs[i][0], costs[i][1]);
            answer += costs[i][2];
        }
    }
    
    return answer;
}

 

- 프림 알고리즘

int answer = 0;

	vector<vector<int>> graph(n, vector<int>(n));

	for (int i = 0; i < costs.size(); ++i) {
		graph[costs[i][0]][costs[i][1]] = costs[i][2];
		graph[costs[i][1]][costs[i][0]] = costs[i][2];
	}

	vector<int> visited;
	vector<int> unvisited;

	visited.push_back(0);
	for (int i = 1; i < n; ++i) {
		unvisited.push_back(i);
	}

	for (int i = 1; i < n; ++i) {
		int min = INT_MAX;
		int min_index = 0;

		for (int j = 0; j < i; ++j) {
			for (int k = 0; k < n - i; ++k) {
				if (graph[visited[j]][unvisited[k]] > 0 && min > graph[visited[j]][unvisited[k]]) {
					min = graph[visited[j]][unvisited[k]];
					min_index = k;
				}
			}
		}

		visited.push_back(unvisited[min_index]);
		unvisited.erase(unvisited.begin() + min_index);
		answer += min;
	}

	return answer;