<Programmers> Greedy_섬 연결하기 + MST, Kruskal Algorithm c++

Lv3. 섬 연결하기
참고

💡Summary & Idea

• costs에는 A섬, B섬, A섬과 B섬 사이의 거리의 쌍이 주어진다
• 최소비용으로 n개의 섬을 모두 연결할 수 있도록 한다
• 섬과 섬 사이의 거리를 기준으로 오름차순으로 정렬한 뒤, 섬을 차례대로 연결하고, 모든 섬이 연결될 때까지 반복한다

여기서 비용을 기준으로 정렬한 뒤 차례대로 연결하면 그게 모든 섬을 연결한다고 보장할 수 있을까?

예를들어 costs= {{0,1,1},{0,2,1}, {1,2,2}, {3,4,3}}과 같은 예시가 있다고 했을 때, 마지막 값(비용)을 기준으로 정렬을 했다고 했을 때도 순서는 같다. 하지만 여기서 결과적으로 2-0-1-2 섬은 이렇게 연결되어 있고 3-4섬은 연결되어 있지 않다.

따라서 여기서 고려해야 할 점은 모든 섬이 한 집합에 포함되느냐 (하지만 문제에서 연결되지 않는 경우는 없다고 했다), 연결된 섬이 사이클을 이루지 않느냐 (이미 섬집합에 포함되어 있느냐)이다.

여기서 추가하려는 섬이 이미 섬집합에 포함되어 있는지 아닌지 어떻게 알 수 있을까? 깊이 우선 탐색하며 모두 탐색해보아야 할까? 아니다. 이때 필요한 개념이 Kruskal Algorithm이다.

📜Kruskal Minimum Spanning Tree Algorithm

1. 모든 간선을 가중치의 오름차순으로 정렬
2. 스패닝 트리에 하나씩 추가
3. 가중치가 작다고 무조건 간선을 트리에 더하는 것이 아니라, 사이클이 생기지 않는 경우에만 트리에 더해준다
4. 상호 배타적 집합 자료구조를 사용하여 양 끝 점이 같은 컴포넌트에 속해 있는지 확인하고 그렇지 않다면 두 컴포넌트를 합친다.

struct DisjointSet {
	vector<int> parent;
	DisjointSet(int n) : parent(n) {
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}
	int find(int u) const {
		if (u == parent[u]) return u;
		return find(parent[u]);
	}
	void merge(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		parent[u] = v;
	}
};

const int MAX_V = 100;
int V; //num of vertex
//pair<jointed vertex number, cost>
vector<pair<int, int>> adj[MAX_V];
int kruskal(vector<pair<int, int>>& selected) {
	int ret = 0;
	selected.clear();

	vector<pair<int, pair<int, int>>> edges;
	for (int u = 0; u < V; ++u) {
		for (int i = 0; i < adj[u].size(); ++i) {
			int v = adj[u][i].first; int cost = adj[u][i].second;
			edges.push_back(make_pair(cost, make_pair(u, v)));
		}
	}
	//order by cost
	sort(edges.begin(), edges.end());

	DisjointSet sets(V);
	for (int i = 0; i < edges.size(); i++) {
		int cost = edges[i].first;
		int u = edges[i].second.first;
		int v = edges[i].second.second;

		if (sets.find(u) == sets.find(v)) continue;
		sets.merge(u,v);
		selected.push_back(make_pair(u, v));
		ret += cost;
	}
	return ret;
}

• find 함수에서는 현재 노드의 부모 노드를 찾을 때까지 반복한다.
• 그 후 합치려는 두 노드의 부모 노드가 같을 경우, 이 두 노드는 같은 집합에 있다는 뜻이므로 연산을 하지 않는다
• 그렇지 않은 경우 한 노드(u)의 부모 노드를 (v)로 만들어줌으로써 두 노드를 합친다

이 문제에서 이 알고리즘을 적용해 문제를 해결해본다.

1📚 vector<int> parents

• 각 섬의 부모 섬을 저장하는 벡터를 만든다
• 처음에는 모든 섬이 자신을 부모 섬으로 가진다

for (int i=0; i<n; i++) parents[i]=i;

• 합치려는 두 섬이 같은 루트 섬을 가지고 있다면 합치지 않는다
• 합칠 때는 부모 섬의 값이 더 작은 값을 부모 섬으로 가진다 (반대가 되어도 상관 없다. 그냥 규칙을 만들어주기 위함이다)

bool merge (int u, int v) {
  
    int a=find(u);
    int b=find(v);
 
    if (a==b) return false; 
    if (a>b) parents[a]=b;
    else parents[b]=a;

    return true;
}

📚2. Solution

• costs를 마지막 값, 비용을 기준으로 오름차순 정렬한다

bool compare (const vector<int>&a, const vector<int>&b) {
    if (a[2]<b[2]) return true;
    return false;
}

sort(costs.begin(), costs.end(), compare);

• 그 후 두 costs[i][0], costs[i][1] 두 섬을 합칠 수 있다면 costs[i][2]값을 계속 더해준다

Source Code

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

using namespace std;
const int MAX=100;

vector<int> parents(MAX);

bool compare (const vector<int>&a, const vector<int>&b) {
    if (a[2]<b[2]) return true;
    return false;
}

int find (int u) {
    if (u==parents[u]) return u;
    return find(parents[u]);
}

bool merge (int u, int v) {

    int a=find(u);
    int b=find(v);

    if (a==b) return false; 
    if (a>b) parents[a]=b;
    else parents[b]=a;

    return true;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
  
    for (int i=0; i<n; i++) parents[i]=i;
    //order by cost
    sort(costs.begin(), costs.end(), compare);
 
    for (int i=0; i<costs.size(); i++) {
        int u=costs[i][0];
        int v=costs[i][1];
        int cost=costs[i][2];
    
        if (merge(u,v)) answer+=cost;
    }

    return answer;
}