[프로그래머스 문제풀이] 29. 섬 연결하기

개요

오랫동안 고민했는데도 문제가 안 풀려서 결국 해답을 찾아봤다. 이 문제는 크루스칼 알고리즘으로 푸는 문제이다.
학교에서 배운 것 같긴 한데 알고리즘 공부를 많이 안 하다보니 어떤 알고리즘인지 잊어먹었다.
그래서 이번 기회에 최소신장트리와 크루스칼 알고리즘의 개념에 대해 확실하게 공부했다.

---

최소신장트리

연결 그래프 중에 정점의 개수가 n이라고 했을 때 간선의 개수가 n-1일 때 이 그래프는 신장트리라고 한다.
만약에 간선마다 가중치가 있다고 한다면 연결 그래프에서 간선을 선택하여 신장트리를 만들 때 가중치가 최소가 되는 신장트리가 있을 것이다. 이것을 최소신장트리라고 부른다.

---

크루스칼 알고리즘

크루스칼 알고리즘은 그리디 메서드를 이용하는 최소신장트리를 구하는 알고리즘이다. 시간복잡도는 O(NlogN)이다.

크루스칼 알고리즘 과정
1. 간선의 가중치를 기준으로 정렬
2. 정렬된 간선을 순서대로 선택
3. 사이클이 생기는 지 검사하기
4. 사이클이 생기지 않았다면 최소신장트리 집합에 추가
5. 위의 과정 반복

---

코드 설명

저번에 알게 된 함수 객체와 람다를 이용하여 함수를 대체하는 방법을 사용했다.
이것으로 island 벡터를 전역으로 보내지 않아도 된다.

벡터의 인덱스를 섬 번호, 값을 부모 섬 번호로 삼는다.

벡터에다 섬 번호를 넣으면 부모 섬이 갱신된다.
이 과정을 반복하면 부모 섬이 같은 두 섬이 존재할 때 사이클이 생겼다는 것을 알 수 있다.

---

🎉완성코드

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

using namespace std;

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<int> island(101);

    //섬 저장
    for (int i = 0; i < n; i++) {
        island[i] = i;
    }
    // 1. 비용이 적은순으로 정렬
    sort(costs.begin(), costs.end(), [](vector<int> a, vector<int> b) {
        return a[2] < b[2]; });

    function<int(int)> findParent = [&](int idx)  -> int {
        if (island[idx] == idx)
            return idx;
        return island[idx] = findParent(island[idx]);
    };

    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;
}

섬 연결하기 문제 링크