[ 프로그래머스 섬 연결하기 (Lv3) ] (C++)

프로그래머스의 섬 연결하기(Lv3) 문제이다.

[ 문제풀이 ]

모든 섬이 통행할 수 있도록 연결하되 그 비용을 최소로 하는 값을 구해야 하는 문제이다.

본인은 이 문제를 최소스패닝트리(Minimal Spanning Tree)를 이용해서 접근해보았다.

'그래프에서 모든 노드를 포함하면서 순환되는 경로를 제거하고, 그 가중치의 합이 최소가 되도록 만든 그래프' 와,

'주어진 섬들 사이에서, 모든 섬이 통행할 수 있도록 연결하되, 그 비용이 최소가 되도록 만드는 것' 이 동일한 맥락이기 때문에

최소스패닝트리를 이용해서 구현해 보았다.

최소 스패닝 트리를 구현하는 대표적인 알고리즘으로는 '크루스칼 알고리즘' 과 '프림 알고리즘' 이 있다.

아직 위의 알고리즘들에 대해서 잘 모른다면 아래의 글을 읽고 오자.

[ 크루스칼 알고리즘 알아보기(Click) ]

[ 프림 알고리즘 알아보기(Click) ]

이 문제는 크루스칼 혹은 프림 알고리즘을 구현만 할 줄 안다면 추가적인 부분은 설명이 필요가 없을 것 같다.

따라서 설명은 위의 글들로 대체하겠다. 소스코드는 크루스칼, 프림 알고리즘 2가지 모두 첨부하겠다.

[ 크루스칼 알고리즘 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
#define MAX 105
using namespace std;
 
int Parent[MAX];
vector<pair<int, pair<int, int>>> Edge;
 
int Find_Parent(int A)
{
    if (A == Parent[A]) return A;
    return Parent[A] = Find_Parent(Parent[A]);
}
 
bool Same_Parent(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    if (A == B) return true;
    return false;
}
 
void Union(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    Parent[B] = A;
}
 
int solution(int n, vector<vector<int>> costs)
{
    int answer = 0;
    for (int i = 0; i< n; i++) Parent[i] = i;
    for (int i = 0; i < costs.size(); i++)
    {
        int Node1 = costs[i][0];
        int Node2 = costs[i][1];
        int Cost = costs[i][2];
        Edge.push_back(make_pair(Cost, make_pair(Node1, Node2)));
    }
    sort(Edge.begin(), Edge.end());
    for (int i = 0; i < Edge.size(); i++)
    {
        int Cost = Edge[i].first;
        int Node1 = Edge[i].second.first;
        int Node2 = Edge[i].second.second;
 
        if (Same_Parent(Node1, Node2) == false)
        {
            Union(Node1, Node2);
            answer = answer + Cost;
        }
    }
    return answer;
}

[ 프림 알고리즘 소스코드 ]

#include <string>
#include <vector>
#include <queue>
 
#define MAX 105
using namespace std;
 
bool Visit[MAX];
vector<pair<int, int>> V[MAX];
int solution(int n, vector<vector<int>> costs)
{
    int answer = 0;
    for (int i = 0; i < costs.size(); i++)
    {
        int N1 = costs[i][0];
        int N2 = costs[i][1];
        int Cost = costs[i][2];
        
        V[N1].push_back(make_pair(N2, Cost));
        V[N2].push_back(make_pair(N1, Cost));
    }
    
    priority_queue<pair<int, int>> PQ;
    for (int i = 0; i < V[0].size(); i++)
    {
        int Next = V[0][i].first;
        int nCost = V[0][i].second;
        PQ.push(make_pair(-nCost, Next));
    }
    Visit[0] = true;
    while (PQ.empty() == 0)
    {
        int Distance = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        if (Visit[Cur] == false)
        {
            Visit[Cur] = true;
            answer = answer + Distance;
 
            for (int i = 0; i < V[Cur].size(); i++)
            {
                int Next = V[Cur][i].first;
                int nDistance = V[Cur][i].second;
                if (Visit[Next] == false) PQ.push(make_pair(-nDistance, Next));
            }
        }
    }
    return answer;
}