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

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

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

---

 

-풀이-

최소 비용으로 모든 섬이 서로 통행가능하도록 만드는것은 최소신장트리 알고리즘을 사용해주면 된다. 

최소신장트리 알고리즘을 사용하기 위해선,

 1. 먼저 각 도로(간선)들을 비용을 기준으로 오름차순 정렬을 해준뒤,

 2. 작은 간선부터 차례대로 검사해가며, 두 정점이 같은 그룹에 속하지 않는다면, 같은그룹으로 묶어주면서, 그 간선을 최소신장트리의 간선으로 채택을 해주면 된다.

 3. 이미 같은 그룹이라면, 앞에서 더 적은 비용으로 갈 수 있는 간선을 선택했으므로 무시해주면 된다.

 

-시간 복잡도-

costs 벡터의 사이즈를 N,정점의 개수를 V라고 한다면,

1. 정렬단계에서 c++ algorithm헤더파일에 있는 sort함수를 사용했으므로, 퀵소트의 기대시간 O(NlogN)

2. 반복문 단계에서 findParent함수는 O(V)이지만, V는 최대 100이므로, 상수시간으로 쳐도된다. 이에따라 unionParent함수 또한 상수시간이 걸린다.

 

따라서 최종적으로 시간복잡도는 O(NlogN)이 된다.

 

-코드-

 

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

int parent[100];
bool compare(vector<int> a,vector<int> b){
    return a[2]<b[2];
}

int findParent(int a){
    if(a==parent[a]) return a;
    else return findParent(parent[a]);
}

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

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(),costs.end(),compare);
    for(int i=0;i<n;i++) parent[i]=i;
    for(int i=0;i<costs.size();i++){
        int a=costs[i][0];
        int b=costs[i][1];
        int cost=costs[i][2];
        
        //같은그룹이 아니라면 합친다.
        if(findParent(a)!=findParent(b)){
            unionParent(a,b);
            answer+=cost;
        }
    }
    return answer;
}