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

다익스트라를 연습한 뒤에는 이전에 풀었던 최소 스패닝 트리 알고리즘을 복습하였다.

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

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

모든 섬을 최소한의 비용으로 연결한다는 점에서 MST(최소 스패닝 트리)에 관한 문제라는 점을 간파해야 한다.

최소 스패닝 트리의 경우 크루스칼 알고리즘이 편해서 적용했던 것 같다.

가중치가 적은 간선부터 정렬한 뒤, 사이클이 생기지 않는다면 그리디하게 간선을 가져오면 된다.

여기서는 벡터를 쓴 후 정렬했는데, 우선순위 큐를 써도 괜찮다.

 

그리고 사이클을 검사하는 것은 Union-Find 알고리즘을 사용했다.

 

✔︎ union(a, b) - a와 b중 최상단 부모를 다른 노드의 최상단 부모의 부모로 만들어서 합치기(사이클이 아님을 전제해야함)

✔︎ find(node) - 최상단에 위치한 부모노드, 즉 node가 속한 부모 리턴

 

find를 써서 부모가 다르면(즉 사이클이 아니라면) union

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
// MST - Kruskal
using namespace std;
struct island {
    int cost;
    int a;
    int b;
};
vector<island> islands;
int parent[100];
bool cmp(const island &a, const island &b);
void unionNode(int a, int b);
int find(int node);
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int visit = 0;
    for(int i = 0;i < n;i++){
        parent[i] = i;
    }
    for(int i = 0; i < costs.size();i++){
        islands.push_back({costs[i][2], costs[i][0], costs[i][1]});
    }
    //cost 오름차순 정렬
    sort(islands.begin(), islands.end(), cmp);
    for(int i = 0; i < islands.size();i++){
        for(int i = 0;i < n;i++){
            cout << parent[i] << " ";
        }
        cout << endl;
        if(find(islands[i].a) != find(islands[i].b)){
            cout << islands[i].a << " " << islands[i].b << " " << islands[i].cost << endl;
            unionNode(islands[i].a, islands[i].b);
            answer += islands[i].cost;
            
        }
        else {
            cout << "looop" << endl;
            cout << islands[i].a << " " << islands[i].b << " " << islands[i].cost << endl;
        }
    }
    return answer;
}

bool cmp(const island &a, const island &b){
    if(a.cost < b.cost) return true;
    else return false;
}

void unionNode(int a, int b){
    int pa = find(a);
    int pb = find(b);
    if(pa < pb){
        parent[pb] = pa;
    }
    else {
        parent[pa] = pb;
    }
}

int find(int node){
    if(parent[node] == node){
        return node;
    }
    return parent[node] = find(parent[node]);
}

union을 이해하는 데에는 그렇게 어렵지 않으나 find는 특이하다고 생각이 들 수 있다.

최상단 부모 노드의 경우에는 parent[node] == node이므로 즉시 node 값을 리턴한다.

하지만 그렇지 않은 경우에는 부모 노드를 타고 타고 올라가서 최상단 부모 노드까지 도달해서 리턴하는 방식이다.

이를 반복적으로 진행할 경우 비효율적이기 때문에 아예 해당 노드에 최상단 부모 노드를 한 번 찾으면 기록해두면 된다.