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

1. 문제

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

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

 

2. 풀이

네트워크와 비슷해보이지만 MST문제로 크루스칼 알고리즘을 사용해야한다.

 

1) 비용이 작은 순으로 정렬한다.

2) 최소 비용으로 다리를 연결하고 싸이클이 생기는지 확인한다.

1번 섬과 2번 섬이 연결되면 island[1] = 2, island[2] = 1이 된다.

3) 싸이클이 생기지 않으면 두 섬 사이에 다리를 연결한다.

1) ~ 3) 을 costs 길이만큼 반복!!

 

*크루스칼 알고리즘: https://hyeri0903.tistory.com/99

[Algorithm] Kruskal Algorithm (크루스칼 알고리즘)

3. 코드

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

using namespace std;

vector<int> island(101);

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

int findParent(int idx){
    if(island[idx] == idx)
        return idx;
    return island[idx] = findParent(island[idx]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    //섬 저장
    for(int i=0; i<n; i++){
        island[i] = i;
    }
    // 1. 비용이 적은순으로 정렬
    sort(costs.begin(), costs.end(), cmp);
    
    for(int i=0; i<costs.size(); i++){
        int start = findParent(costs[i][0]);
        int end = findParent(costs[i][1]);
        int cost = costs[i][2];
        
        //2. cycle이 만들어지지 않으면 다리 추가
        if(start!=end){
            answer+=cost;
            island[end] = start;
        }
        
    }
    

    return answer;
}