Programmers - 섬 연결하기

---

title: Programmers - 섬 연결하기
date: 2022-08-12
tags:

• Algorithm
• Graph
• Kruskal

---

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

문제 요약

n개의 섬이 존재하며, 섬을 잇는 다리와 다리의 비용이 주어진다.
모든 섬이 연결되도록 하는 최소의 다리 비용을 return한다.

문제 풀이

Graph 문제로, Kruskal 알고리즘을 알고 있는지 확인하는 문제이다.


Kruskal 알고리즘은 가장 적은 비용의 edge부터 확인하며 두 vertex의 가장 높은 parent가 같지 않을 경우 해당 edge를 추가한다.
같은 parent를 가진다면 이미 서로 연결되어 있는 상태로, 더 연결할 필요가 없다.
주어진 배열은 섬 2개, 그리고 다리의 비용을 하나로 묶어서 vector로 넘겨주었다.
비용 기준 오름차순으로 정렬을 한 후, 앞에서부터 확인하면 된다.
vNoedParent vector는 각 섬의 parent를 알려준다. 계속 올라가다보면 가장 높은 parent를 찾을 수 있다.
가장 높은 parent가 같지 않다면 새로운 parent로 갱신하고 비용을 더해준다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;

int iGetParent ( vector < int > & vNodeParent , int iIndex )
{
    while ( -1 != vNodeParent [ iIndex ] )
    {
        iIndex = vNodeParent [ iIndex ] ;
    }


    return iIndex ;
}

int solution ( int n , vector < vector < int > > costs )
{
    int answer = 0 ;
    int iCostSize = costs.size () ;
    vector < int > vNodeParent ( n , -1 ) ;
    int iCount = 0 ;



    for ( int i = 0 ; i < iCostSize ; ++i )                    // Sort each vector
    {
        std :: sort ( costs.begin () , costs.end () , [] ( vector < int > & v1 , vector < int > & v2 ) { return v1 [ 2 ] < v2 [ 2 ] ; } ) ;
    }

    for ( int i = 0 ; ( iCount < n - 1 ) && ( i < iCostSize ) ; ++i )        // Kruskal
    {
        int iStart = iGetParent ( vNodeParent , costs [ i ] [ 0 ] ) ;
        int iEnd = iGetParent ( vNodeParent , costs [ i ] [ 1 ] ) ;
        int iCost = costs [ i ] [ 2 ] ;

        if ( iStart > iEnd )                // Swap
        {
            iStart += iEnd ;
            iEnd = iStart - iEnd ;
            iStart -= iEnd ;
        }

        if ( iStart != iEnd )
        {
            vNodeParent [ iEnd ] = iStart ;
            answer += iCost ;
            ++ iCount ;
        }
    }


    return answer ;
}