[프로그래머스 lv3] 섬 연결하기 풀이

해설

MST(최소 신장 트리)를 구하는 문제이다.

최소 신장 트리를 구하는 문제는 크루스칼 알고리즘이나 프림 알고리즘을 이용하여 해결할 수 있는데, 그 중 크루스칼 알고리즘으로 해결하였다.

 

먼저, 정점을 잇는 간선을 길이가 짧은 순으로 나열한다.

간선을 탐색하면서 두 정점이 다른 그룹이면 두 정점을 하나의 그룹으로 합치고 해당 간선을 선택한다. 

이미 두 정점이 같은 그룹에 있으면 패스한다.

크루스칼 알고리즘에 대한 자세한 설명은 최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘를 참조하면 좋다.

 

 

코드

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<iii> edge;
vector<int> nrank(100, 1);
vector<int> parent(100, 0);


void initialize(int n) {

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

int find(int u) {

    if (parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

void merge(int u, int v) {

    u = find(u);
    v = find(v);

    if (u == v) return ;
    if (nrank[u] > nrank[v]) swap(u, v);
    else if (nrank[u] == nrank[v]) nrank[v]++;
    parent[u] = v;
}

void setGraph(const vector<vector<int>>& costs) {

    for (auto v : costs)
        edge.push_back({v[2], v[0], v[1]});
    sort(edge.begin(), edge.end());
}

int solution(int n, vector<vector<int>> costs) {

    setGraph(costs);
    initialize(n);

    int ans = 0;
    for (auto [w, u, v] : edge) {
        if (find(u) == find(v)) continue;
        merge(u, v);
        ans += w;
    }
    return ans;
}