[Programmers] Lv3. 섬 연결하기 | C++

🔗문제 보러가기

프로그래머스

 

🧑‍💻풀이 과정

 

🔗최소 신장 트리(MST, Minimum Spanning Tree)를 활용하는 문제입니다. 최소 신장 트리를 구축하는 과정에서 크루스칼(Kruskal) 또는 프림(Prim)의 알고리즘이 사용되며, 저는 크루스칼(Kruskal)의 알고리즘을 사용하여 풀었습니다.

 

신장 트리의 조건 중 하나로 사이클이 있으면 안된다가 있는데, 분리 집합(Disjoint set)의 개념인 🔗유니온 파인드(Union Find)라 불리는 자료구조로 쉽게 점검할 수 있습니다.

 

이번 기회에 공부하여 개념을 학습 후, 이를 활용하여 문제를 풀어보았습니다. 제가 이걸 알았더라면, NC Soft 코딩 테스트에서 한 문제는 그냥 풀고 넘어갔을텐데 말이죠... 아쉽네요.

 

✏️소스 코드 및 결과

#include <vector>
#include <algorithm>
using namespace std;

class DisjointSet
{
public:
    DisjointSet(int n) : parent(n), rank(n, 1)
    {
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int Find(int node)
    {
        if (parent[node] == node)
            return node;
        return parent[node] = Find(parent[node]);
    }

    void Merge(int node1, int node2)
    {
        node1 = Find(node1), node2 = Find(node2);
        if (node1 == node2)
            return;

        if (rank[node1] > rank[node2])
            swap(node1, node2);

        parent[node1] = node2;

        if (rank[node1] == rank[node2])
            rank[node2]++;
    }

    bool IsInSameSet(int node1, int node2)
    {
        node1 = Find(node1), node2 = Find(node2);
        return node1 == node2;
    }
private:
    vector<int> parent;
    vector<int> rank;
};

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    DisjointSet ds(n);
    
    sort(costs.begin(), costs.end(), [](const vector<int>& c1, const vector<int>& c2) { return c1[2] < c2[2]; });
    for (const auto& cost : costs)
    {
        int node1 = cost[0], node2 = cost[1];
        if (ds.IsInSameSet(node1, node2))
            continue;

        ds.Merge(node1, node2);
        answer += cost[2];
    }

    return answer;
}