프로그래머스 섬 연결하기 c++, Kotlin (MST)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42861

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

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

풀이

'프로그래머스 / 탐욕법(Greedy) / 섬 연결하기'로 분류되어 있는 문제이다.

 

음.. 알고 있는 알고리즘을 응용하고 구현해서 풀어보려고 애썼지만,

결국 구글링을 해보니 크루스칼 or 프림 알고리즘을 사용해야 최소 스패닝 트리를 구현하는 문제였다.

처음 보는 알고리즘이었고, 프림보단 크루스칼이 동작 방식이 마음에 들어,

동빈나님의 강의와 얍문님의 포스팅을 보고 공부했다.

알고리즘에 대한 내용은 노트에만 필기했는데, 블로그에 포스팅하여

기록해도 괜찮을 것 같다. 조금 여유로워지면, 알고리즘 공부 내용과, 
언어 공부 내용도 포스팅할 예정이다.

 

풀이는 크루스칼 알고리즘을 알고 있다면 따로 설명할 게 없을 정도로, 크루스칼 알고리즘 그 자체인 문제이다.

간선들의 가중치를 오름차순으로 정렬하고, 가중치가 낮은 간선부터 확인하여, 간선을 연결했을 때,
그래프가 사이클을 이루면 무시하고, 사이클을 이루지 않으면 간선을 연결한다.

가중치가 최솟값인 간선을 우선적으로 연결했기 때문에, 최솟값이 아닌 간선은 무시하게 되고,
이를 모두 연결하면 모든 정점이 연결된다.

 

코드(c++)

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

int getParent(vector<int> &parent, int x){
    if(parent[x]==x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

void unionParent(vector<int> &parent, int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if( a<b) parent[b] = a;
    else parent[a] = b;
}

bool findParent(vector<int> &parent, int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a==b) return 1;
    else return 0;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
vector<pair<int,pair<int,int>>> vt;
    vector<int> parent;
    for(int i=0; i<n;i++){
        parent.push_back(i);
    }
    for(int i=0; i<costs.size();i++){
        vt.push_back({costs[i][2],{costs[i][0],costs[i][1]}});
    }
    sort(vt.begin(),vt.end());
    for(int i=0; i< vt.size();i++){

      if(!findParent(parent, vt[i].second.first, vt[i].second.second)){
          answer+= vt[i].first;
          unionParent(parent, vt[i].second.first, vt[i].second.second);
      }
    }

    return answer;
}

코드(Kotlin)

//https://programmers.co.kr/learn/courses/30/lessons/42861
class Solution {
    fun getParent(parent : IntArray, x : Int): Int{
        return if(parent[x]==x) x else getParent(parent,parent[x]).also{ parent[x] = it}
    }
   fun unionParent(parent : IntArray, a : Int, b : Int){
       val x = getParent(parent, a)
       val y = getParent(parent, b)
       if(x<y){
           parent[y]=x
       }
       else{
           parent[x]=y
       }
   }
   fun findParent(parent : IntArray, a : Int, b : Int) : Boolean{
       val x = getParent(parent, a)
       val y = getParent(parent, b)
       return if(x==y) true else false
    }
    
    fun solution(n: Int, costs: Array<IntArray>): Int {
        var answer = 0
        val parent = IntArray(n){it}
        //비용 별로 오름차순
        costs.sortWith(Comparator(){a,b ->a[2]-b[2]})

        for(i in costs.indices){
            if(!findParent(parent,costs[i][0],costs[i][1])){
                //부모가 같지 않다면 (싸이클이 없다면)
                unionParent(parent,costs[i][0],costs[i][1])
                answer+=costs[i][2]
            }
        }
        return answer
    }
}