문제 푼 날짜 : 2021-08-31

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42861

접근 및 풀이

크루스칼 알고리즘(Kruskal Algorithm)을 이용하면 쉽게 풀 수 있는 문제였다. 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 만드는데 이용되는 대표적 알고리즘이다.
각 노드 사이에 비용이 있는 간선이 존재할 때, 모든 노드를 연결하되 최소한의 비용으로 연결하는 알고리즘이다.

1. 문제에 주어진 연결 정보를 비용에 대하여 오름차순으로 정렬한다.
2. 정렬된 연결 정보를 탐색하며 두 섬을 연결했을 때 사이클을 이루지 않는다면 비용을 더해주고, 연결해준다.

크루스칼 알고리즘에 대한 공부는 https://blog.naver.com/ndb796/221230994142 를 참고하였다.

코드

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

using namespace std;

bool compare(vector<int> v1, vector<int> v2) {
    return v1[2] < v2[2];
}

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

void Union(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a > b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
}

bool Find(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    
    if (a == b) {
        return true;
    } else {
        return false;
    }
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int parent[101];
    
    for (int i = 0; i <= n; i++) {
        parent[i] = i;
    }
    
    sort(costs.begin(), costs.end(), compare);
    for (auto c : costs) {
        if (Find(parent, c[0], c[1]) == false) {
            answer += c[2];
            Union(parent, c[0], c[1]);
        }
    }
    return answer;
}

결과

피드백

공부하면 할수록 알고리즘 수업때 배웠던 것들이 튀어나온다...