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

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

크루스칼 알고리즘이나 프림 알고리즘을 알고 있다면 풀 수 있는 문제입니다.

 

문제 접근법

• 크루스칼 알고리즘을 사용하기 위하여 비용에 관하여 오름차순으로 정렬해줍니다.
• 자기 자신이 루트의 최상위로 인식하도록 초기화를 해줍니다.
• 모든 노드를 탐색하면서 진행하되, 현재 노드와 다음 노드가 루트가 다를 경우 연결합니다.

아래는 코드입니다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int root[100];
vector<int> v;
 
bool checkCost(vector<int> &a, vector<int> &b)
{
    return a[2] < b[2];
}
 
int findRoot(int node)
{
    if(node == root[node]) 
        return node;
    else 
        return root[node] = findRoot(root[node]);
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int len = costs.size();
    
    sort(costs.begin(), costs.end(), checkCost);
    
    for(int i = 0; i < n; i++)
        root[i] = i;
    
    for(int i = 0; i < len; i++)
    {
        int current = findRoot(costs[i][0]);
        int next = findRoot(costs[i][1]);
        int cost = costs[i][2];
        
        if(current != next)
        {
            root[end] = current;
            answer += cost;
        }
    }
    
    return answer;
}