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

 

문제 링크: programmers.co.kr/learn/courses/30/lessons/42861

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

 

풀이

 

Kruskal(크루스칼) 알고리즘을 이용해서 문제를 해결했다. 

 

• 섬 사이에 다리 연결에 드는 비용이 적은 순서대로 costs를 정렬한다. 
• set[i]를 초기화해준다. set[i]는 i번째 노드의 부모 노드를 저장하는 배열이다. 부모노드란 i번째 노드와 연결된 모든 노드 중에서 인덱스가 가장 작은 노드이다. 
• 예를 들어 노드0과 노드1이 연결되면 set[0] = 0, set[1] = 0이 저장된다. 
• 정렬된 costs를 모두 탐색할 때까지 다음을 반복한다. 
  - 연결할 두 노드의 parent가 다르다면( 연결 가능 상태 )
  - 두 노드를 연결하고 parent를 set에 저장한다. 

 

 

* Kruskal's Algorithm 참고

2021/01/26 - [알고리즘/알고리즘] - [알고리즘] MST(Minimum Spanning Tree, 최소 신장 트리) - Prim(프림), Kruskal(크루스칼) 알고리즘

[알고리즘] MST(Minimum Spanning Tree, 최소 신장 트리) - Prim(프림), Kruskal(크루스칼) 알고리즘

 

 

 

 

소스코드

 

#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
int set[101];   // node의 parent를 저장하는 배열
 
int getParent(int node) {
    if(set[node] == node) return node;
    return set[node] = getParent(set[node]);
}
 
bool cmp(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
 
    for(int i = 0; i < n; i++)
        set[i] = i;
    
    sort(costs.begin(), costs.end(), cmp);  // 비용을 오름차순 정렬
 
    for(int i = 0; i < costs.size(); i++) {
        int start = getParent(costs[i][0]);
        int end = getParent(costs[i][1]);
        int cost = costs[i][2];
 
        if(start != end) {  // cycle이 만들어지지 않을 경우 다리를 추가
            answer += cost;
            set[end] = start;
        }
    }
 
    return answer;
}

 

테스트 결과