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

프로그래머스: 섬 연결하기

문제 링크

처음에는 아주 단순하게 생각해서 비용을 오름차순으로 정렬한 후에 선택된 다리의 수가 n-1개 이상이 되면 모든 섬을 방문하는지 확인하도록 했다. 결과는 당연히 틀렸다. 아마 사이클을 고려하지 않았기 때문인 것 같다. 질문하기를 보니 크루스칼 알고리즘(Kruskal Algorithm)을 사용했다는 말이 보였고, 바로 사용해 보았더니 쉽게 통과했다. 알고리즘 수업 이후로 잊고 살았던 이 친구를 다시금 리마인드하는 계기가 되었다.

Kruskal Algorithm

가장 적은 비용으로 모든 노드를 연결하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만드는 알고리즘이라고 할 수 있다. 모든 노드를 가장 적은 비용으로 연결시키기 위해 모든 간선(비용) 정보를 오름차순으로 정렬 후 비용이 적은 간선부터 그래프에 포함시킨다. 다만, 사이클을 형성하는지 확인해 주어야 한다. 최소 비용으로 모든 노드를 연결만 하는 것이기 때문에 사이클이 포함되어서는 안 되고, 되어야 할 이유도 없다. 알고리즘을 적용하는 순서는 아래와 같다.

1. 오름차순으로 정렬된 간선을 그래프에 포함시킨다.
2. 포함시키기 전 사이클을 형성하는지 확인한다.
3. 사이클을 형성하는 경우 포함시키지 않는다.
4. 최소 비용 신장 트리가 완성될 때까지 위의 과정을 반복한다.

사이클이 발생하는지의 여부는 Union-Find 알고리즘으로 간단하게 알 수 있다.

Union-Find

처음에는 모든 노드가 연결되지 않고 자기 자신만을 집합의 원소로 가진다. 이때의 부모 노드는 자기 자신이 된다. 노드가 연결되면 한 노드는 부모 노드가 되고, 한 노드는 자식 노드가 된다. 일반적으로 숫자가 작은 쪽이 부모 노드가 된다. 이렇게 부모 노드를 설정해 주는 것은 union이라고 한다.

0의 경우 0의 부모인 1은 2를 부모로 가진다. 그러므로 0의 부모는 2가 되는데, 이를 단번에 알 수 있도록 하기 위해서 재귀 함수가 사용된다. find는 이런 과정을 거친 두 노드의 부모가 같은지를 확인한다.

풀이

크루스칼 알고리즘과 union-find를 적용해서 섬 연결하기 문제를 해결할 수 있다. 크루스칼 알고리즘을 적용하는 과정에서, 사이클을 형성하는지 확인하기 위해 union-find 알고리즘을 사용했다.

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

int parent[100];

bool cmp(vector<int> arr1, vector<int> arr2) {
    if(arr1[2] == arr2[2]) {
        if(arr1[0] == arr2[0])
            return arr1[1] < arr2[1];
        else return arr1[0] < arr2[0];
    }
    else return arr1[2] < arr2[2];
}

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

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);

    if(a < b) parent[b] = a;
    else parent[a] = b;
}

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

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int s, e, cost;

    for(int i = 0; i < n; i++)
        parent[i] = i;

    sort(costs.begin(), costs.end(), cmp);

    for(int i = 0; i < costs.size(); i++) {
        s = costs[i][0];
        e = costs[i][1];
        cost = costs[i][2];

        if(!findParent(s, e)) {
            answer += cost;
            unionParent(s, e);
        }
    }

    return answer;
}