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

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

Solution

#include <string>
#include <vector>
#include <algorithm>
#define MAX 101
using namespace std;

int Parent[MAX];

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<pair<int, pair<int, int>>> vec;
    for(int i = 0; i < costs.size(); i++){
        int start = costs[i][0];
        int end = costs[i][1];
        int cost = costs[i][2];
        vec.push_back({cost, {start, end}});
    }
    for(int i = 0 ; i < n; i++) Parent[i] = i;
    sort(vec.begin(), vec.end());
    for(int i = 0; i < vec.size(); i++){
        int start = vec[i].second.first;
        int end = vec[i].second.second;
        int cost = vec[i].first;
        if(!findParent(start, end)){
            answer += cost;
            unionParent(start, end);
        }
    }
    return answer;
}

크루스칼 알고리즘을 활용하는 문제다.

우선 크루스칼 알고리즘에 대해 언급하자면

1. 모든 간선들의 가중치를 오름차순으로 정렬한다.
2. 가중치가 가장 작은 간선을 선택한다.
3. 2에서 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 위의 과정을 반복한다.

이러한 알고리즘이다. MST를 만드는 게 이 문제의 핵심이다.

int Parent[MAX];

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}

Union Find 에 필요한 코드들이다. 어렵게 생각할 건 없고 Parent 배열을 처음에는 모든 노드에 대해 자신으로 초기화 시켜둔다(Solution 함수에서 자세히 나온다.).
그리고 이 세가지 함수를 토대로 크루스칼 알고리즘을 구현하면 된다. 코드 자체는 어렵지 않다. Union Find 기법을 쓰기 위해 반드시 숙지해야하는 세 함수니까 외우다시피 알고있는 게 좋다. (Index tree 같은 기법을 쓰기위해서도 필요하다. )

다시 Solution 함수를 보자.

vector<pair<int, pair<int, int>>> vec;
for(int i = 0; i < costs.size(); i++){
    int start = costs[i][0];
    int end = costs[i][1];
    int cost = costs[i][2];
    vec.push_back({cost, {start, end}});
}
for(int i = 0 ; i < n; i++) Parent[i] = i;
sort(vec.begin(), vec.end());

각 데이터간에 단방향 그래프는 아니지만 현재로써는 직접 탐색하는것도 아니고 그 경로에 대한 정보만 있으면 되니까 신경쓰지말고 입력한다.
그 후 각 노드들은 모두 본인을 Parent로 보고 있도록 세팅해둔다. 또한 모든 노드들을 cost 기준으로 정렬시킨다.

for(int i = 0; i < vec.size(); i++){
    int start = vec[i].second.first;
    int end = vec[i].second.second;
    int cost = vec[i].first;
    if(!findParent(start, end)){
        answer += cost;
        unionParent(start, end);
    }
}
return answer;

그 후 하나씩 꺼내가며 해당 경로에 두 시작점과 끝점이 같은 Parent를 공유하지 않는다면(연결되어있지 않다면) 해당 경로를 연결하고 answer에 cost를 저장한다.

어차피 오름차순 정렬이니까 최소한의 비용을 가지는 연결이 자동으로 완성된다.

MST, 크루스칼 알고리즘에 대한 개념이 있다면 풀 수 있는 문제.