[프로그래머스 섬 연결하기] c++ (풀이,코드, 크루스칼 알고리즘)

문제 링크

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

프로그래머스

 

문제

 

풀이, 코드 (크루스칼 알고리즘)

이 문제를 처음에는 어 그냥 최솟값에 대해서 연결만 하면 끝나는거 아니야? 하면서 코드를 일일히 나열했다.

 

근데 풀다가 생각을 해보니 이럴때 각 노드의 연결 값을 최소화!! 할때 크루스칼 알고리즘을 사용하는것이 기억이 났습니다.

 

크루스칼 알고리즘, 최소신장트리(MST)에 대한 그림과 함께 쉽게 설명👇👇👇

https://bendeng-life.tistory.com/142

크루스칼 알고리즘(kruskal Algorithm), 최소 신장 트리(MST) c++ 구현

 

풀이 순서는 이러합니다

 

1. vector nodes(n,0) 초기화 -> 나중에 부모 노드를 찾기 위해 사용

2. 섬과의 연결되는 다리의 비용을 오름차순으로 정렬

3. 1) 오름차순으로 정렬했으니 사이클을 이제 확인해야 한다. 

        (연결시 nodes[0] = 1 nodes[1] = 0이 됨)

    2) 사이클이 생성되지 않았다면 두 노드를 연결한다. 

 

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

bool costCompare(vector<int> a, vector<int> b){

    return a[2] < b[2];

}

int getParent(int idx, vector<int> nodes){

    if(nodes[idx] == idx)

        return idx;

    return nodes[idx] = getParent(nodes[idx],nodes);

}

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

    int answer = 0;

    vector<int> nodes(n,0);

   

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

    for(int i = 0; i < n;i++){

        nodes[i] = i;

    }

    for(int i = 0; i < costs.size();i++){

        int connect = getParent(costs[i][0],nodes); //연결 시작점

        int connected = getParent(costs[i][1],nodes); // 연결 받는점 -> 물론 양뱡향인데 표현을 위해

        int cost = costs[i][2];

       

        if(connect != connected){

            answer+= cost;

            nodes[connected] = connect;

        }

    }

    return answer;

}