[프로그래머스] 섬 연결하기

[ghdcksgml1]

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

아이디어

딱봐도 최소 스패닝 트리 같아서 풀었더니 바로 풀렸다!

최소 스패닝 트리를 쓰기 위해서는 유니온 파인드를 구현해야하는데

복잡하진 않지만, 코드량이 많아서 아주 귀찮다.

시간복잡도

O(E logV)

소스코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
class Edge{
    public:
    int node[2];
    int distance;
    Edge(int a,int b,int distance){
        this->node[0] = a;
        this->node[1] = b;
        this->distance = distance;
    }
};

vector<Edge> v;

int getParent(int parent[],int x){
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent,parent[x]);
}

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

int findParent(int parent[],int a,int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a==b) return 1;
    return 0;
}



bool compare(Edge a,Edge b){
    return a.distance < b.distance;
}

int solution(int n, vector<vector<int>> costs) {
    for(int i=0;i<costs.size();i++){
        v.push_back({costs[i][0],costs[i][1],costs[i][2]});
        v.push_back({costs[i][1],costs[i][0],costs[i][2]});
    }
    
    sort(v.begin(),v.end(),compare);
    int parent[101];
    for(int i=0;i<n;i++) parent[i] = i;
    
    int sum = 0;
    for(int i=0;i<v.size();i++){
        if(!findParent(parent,v[i].node[0],v[i].node[1])){
            sum += v[i].distance;
            unionParent(parent,v[i].node[0],v[i].node[1]);
        }
    }
    
    return sum;
}

심심해서 프로그래머스 Lv.3 도전했는데 바로 컷당했다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

프로그래머스는 트리를 너무 좋아하는듯;;

[BanApp]

이런것도 있구만 주말에 함 조져본다