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

문제 링크

1. 문제 접근 과정🧐

1. 각 섬이 연결된 다리를 비용 별로 정렬(그리디하게 짧은 것 우선)
2. n개의 섬이 있다면 모두 연결이 되려면 n-1개의 간선이 연결되면 된다는 것을 파악
3. 연결된 간선이 싸이클이 되지 않도록 선택하면서 합치면서 비용을 추가
4. n-1개의 간선이 선택될 때까지 3번을 반복
   
   

2. 시행착오🤯

• 1번과 2번을 생각하고 집합을 사용하여 n개의 섬을 연결하려고 시도하였는데 반례가 있어 실패했다.

  • 예를 들어 (0, 1), (2, 3), (1, 2)가 연결 되어 있고 앞의 2 간선을 택하면 (0, 1, 2, 3)이 되어 (1, 2)는 연결되지 않았는데 종료하게 된다.
    

• 오답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <set>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
    vector<tuple<int, int, int>> c;
    for(auto v : costs) c.push_back({v[2], v[0], v[1]});
    sort(c.begin(), c.end());
    int answer = 0;
    set<int> s;
    for(int i = 0; i < c.size(); i++){
        if(s.size() == n) break;
        int cost = get<0>(c[i]);
        int i1 = get<1>(c[i]);
        int i2 = get<2>(c[i]);
        if(s.find(i1) != s.end() && s.find(i2) != s.end()) continue;
        s.insert(i1);
        s.insert(i2);
        answer += cost;
    }
    return answer;
}

3. 개선한 코드😄

• 집합을 사용하는 것이 아니라 MST(최소신장트리)의 크루스칼 알고리즘을 사용하여 union-find를 하여 해결
  • 문제의 입출력 예시로 정렬하면 [[0,1,1], [1,3,1], [0,2,2], [1,2,5], [2,3,8]] 순서가 된다.
  • 처음에 0, 1을 보면 parent[0] = 0, parent[1] = 1으로 다르므로 union하여 parent는 {0, 0, 2, 3}이 된다.
  • 다음은 1, 3이고 parent[1] = parent[0] = 0, parent[3] = 3으로 다르므로 union하여 parent는 {0, 0, 2, 0}이 된다.
  • 다음은 0, 2이고 parent[0] = 0, parent[2] = 2으로 다르므로 union하여 parent는 {0, 0, 0, 0}이 되어 모든 부모가 같아져 MST가 완성된다.
    
• 정답 코드

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

using namespace std;

int find_parent(int x, vector<int>& parent) {
    if (parent[x] == x) return x;
    return parent[x] = find_parent(parent[x], parent);
}

bool unite(int a, int b, vector<int>& parent, vector<int>& rnk) {
    a = find_parent(a, parent);
    b = find_parent(b, parent);
    if (a == b) return false;
    if (rnk[a] < rnk[b]) swap(a, b);
    parent[b] = a;
    if (rnk[a] == rnk[b]) rnk[a]++;
    return true;
}

int solution(int n, vector<vector<int>> costs) {
    vector<tuple<int, int, int>> edges;
    for(auto v : costs) edges.push_back({v[2], v[0], v[1]});
    sort(edges.begin(), edges.end());
    vector<int> parent(n), rnk(n, 0);
    for (int i = 0; i < n; i++) parent[i] = i;
    int answer = 0;
    int picked = 0;
    for (auto &e : edges) {
        int cost = get<0>(e), u = get<1>(e), v = get<2>(e);
        if (unite(u, v, parent, rnk)) {
            answer += cost;
            picked++;
            if (picked == n - 1) break;
        }
    }
    return answer;
}

4. 회고💭

• 최소신장트리에 대한 지식이 부족했던 것 같다.
  • 이 문제를 통해 해당 이론에 대해 찾아보고 크루스칼 알고리즘에 대해 습득할 수 있었다.
• 다른 최소신장트리 알고리즘은 무엇이 있는지 찾아 공부하고 문제에도 적용할 수 있도록 해야겠다.