Level 3. 섬 연결하기

Level 3. 섬 연결하기

 

 

 

유니온 파인드(Union-Find)
두 노드가 같은 집합에 속하는지 확인하기 위한 서로소 집합(Disjoint set)을 처리하는 알고리즘이다.

유니온 파인드는 대표 노드를 저장하는 1차원 배열을 이용하며, 각 원소의 대표 노드는 자기 자신으로 초기화한다.

• 모두 서로 다른 잡합에 존재함을 뜻한다.

 

유니온(Union) : 특정 2개를 연결해 같은 집합으로 묶는다.

• 대표 노드끼리 연결해주는 작업이다.
• a, b의 대표 노드가 각각 x, y이고 x < y라고 한다면, union(a, b)는 y 위치의 값을 x로 갱신해주는 작업이다.

 

파인드(Find) : 두 노드가 같은 집합에 속해 있는지 확인한다.

• 자신의 대표 노드를 찾는 작업이다.
• 해당 원소의 대표 노드부터 올라가면서, 재귀적으로 자기 자신을 대표 노드로 하는 인덱스를 찾는 작업이다.
• 각 재귀함수를 탈출할 때, 지나온 모든 노드의 대표 노드를 루트 대표 노드로 갱신한다.
  이것을 경로 압축이라고 하며, 그래프를 정돈하고 시간 복잡도를 향상시키는 효과가 있다.

 

 

최소 신장 트리(MST)
그래프에서 최소 비용으로 모든 노드를 연결하는 트리다.
사이클이 포함되면 안 되기에, MST의 노드 개수는 항상 N - 1이다.

• 크루스칼 알고리즘
• 프림 알고리즘

 

크루스칼 알고리즘

1. 인접 행렬이나 인접 리스트가 아닌, 단순 간선 리스트로 그래프를 구현한다.
2. 간선 리스트를 가중치를 기준으로 오름차순 정렬한다.
3. 유니온 파인드를 위한 대표 배열을 자기 자신을 대표 노드로 하도록 초기화한다.
   유니온 파인드는 사이클을 판별하기 위해 사용된다.
4. 가중치가 낮은 간선부터 사이클이 없는 경우에만 연결한다.
   Find 연산에서 대표 노드가 같은 경우, 이를 처리하면 사이클이 발생한다.
5. 연결한 간선 개수가 N - 1이 되면 종료한다.

 

대부분의 설명들에서 대표 노드가 같을 때 연결하면 사이클이 발생해서 안 된다고 하는데, 이는 사실 정확한 설명은 아닌 것 같다.

• Union(a, b)를 통한 연결은 a, b의 대표 노드들의 값을 갱신하는 것을 의미하는데, 대표 노드가 같을 때 Union을 해도 그 대표 노드들의 값은 어차피 같다.
• 대표 배열에서 연결하는 작업 자체에서 문제가 생기는 것이 아니라, 예를 들어 그것을 true로 반환해 연결되었다고 처리할 때, 최소 비용에 가중치를 더하거나 MST의 간선들을 출력할 때 문제가 발생하는 것이다.

 

최소 신장 트리(MST)를 구하는 기본적인 크루스칼 알고리즘 문제다.

• 필수적으로 유니온 파인드 알고리즘을 사용해야 한다.

 

모든 간선을 처리해도 되지만, MST의 간선 개수가 N - 1이면 N개의 노드가 모두 연결되었다는 뜻이므로 종료해도 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int findRep(vector<int>& rep, int i)
{
    if (rep[i] == i)
        return i;

    return rep[i] = findRep(rep, rep[i]);
}

bool unionAB(vector<int>& rep, int a, int b)
{
    int repA = findRep(rep, a);
    int repB = findRep(rep, b);

    if (repA == repB)
        return false;

    rep[repA] = rep[repB] = min(repA, repB);

    return true;
}

int solution(int n, vector<vector<int>> costs)
{
    int answer = 0;
    int nConnected = 0;
    vector<int> rep(n);

    iota(rep.begin(), rep.end(), 0);
    sort(costs.begin(), costs.end(), [](auto& e1, auto& e2) { return e1[2] < e2[2]; });

    for (vector<int>& e : costs)
    {
        if (unionAB(rep, e[0], e[1]))
        {
            answer += e[2];

            if (n - 1 <= ++nConnected)
                break;
        }
    }

    return answer;
}