프로그래머스: 섬 연결하기⭐⭐⭐

체감 난이도 : ⭐⭐
유형 : 그리디, 최소 간선 트리(MST)
걸린 시간: 1시간 초과!

🧐 문제

문제 설명

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

✏️ 풀이 과정

이 문제는 최소 간선 트리(MST) 문제이다. 나의 경우에는 크루스칼 알고리즘(Kruskal Algorithm)을 사용하였다.

크루스칼 알고리즘의 원리는 다음과 같다.

간선 벡터를 길이 기준으로 오름차순 정렬한다.

간선 벡터를 순회한다.
  간선을 추가하였을 때 사이클이 생기는가?

    생긴다면, 해당 간선은 건너뛴다.
    생기지 않는다면, 해당 간선을 추가한다.

  `추가한 간선의 개수`가 `정점 개수 - 1`개라면, break;

이때 사이클이 생기는지는 Union-Find 알고리즘을 사용한다.

Union-Find 알고리즘의 원리는 다음과 같다.

정점 a, b를 입력받는다.

정점 a의 부모를 따라가며, 루트를 찾는다.
정점 b의 부모를 따라가며, 루트를 찾는다.

정점 a와 b의 부모가 같은가?

  같다면, 두 정점은 같은 집합(트리)에 있다.
    -> 사이클이 생긴다.
  다르다면, 두 정점은 다른 집합(트리)에 있다.
    -> 사이클이 생기지 않는다.
    b의 부모를 a로 설정한다.

Union-Find 알고리즘을 최적화하는 방법에는 Union by rank, 경로 압축이 있다.
코드에선 적용해두었지만, 여기에선 따로 설명하지 않고, 링크를 달아둔다.

Union-Find 알고리즘

---

✏️ 나의 풀이

#include <bits/stdc++.h>

using namespace std;

vector<int> p_vec(100, -1);

struct comp {
  bool operator() (vector<int> a, vector<int> b) {
    return a[2] < b[2];
  }
};

int find(int v) {
  int p = p_vec[v];
  if(p < 0) return v;
  
  return p_vec[v] = find(p); // 경로 최적화화
}

bool uni(int v1, int v2) {
  int p1 = find(v1);
  int p2 = find(v2);

  if(p1 == p2) return true;
  // Union by rank 최적화화
  if(p_vec[v1] == p_vec[v2]) p_vec[v1]--;
  if(p_vec[p1] < p_vec[p2]) swap(p1, p2);
  p_vec[p2] = p1;

  return false;
}

int solution(int n, vector<vector<int>> costs) {
  int cnt = 0;
  int result = 0;
  sort(costs.begin(), costs.end(), comp());

  for(auto cost : costs) {
    int v1 = cost[0];
    int v2 = cost[1];
    int d = cost[2];
    
    if(uni(v1, v2)) continue;
    
    cnt++;
    result += d;
    
    if(cnt == n-1) break;
  }
  
  return result;
}

---

✔️ 다른 사람의 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int d[101];

int getParent(int node){
    if(node == d[node]){
        return node;
    }
    else return d[node] = getParent(d[node]);
}

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

int solution(int n, vector<vector<int>> costs) {

    int answer = 0;
    for(int i =0; i<n; i++){
        d[i] = i;
    }
    sort(costs.begin(), costs.end(), compare);
    for(int i=0; i<costs.size(); i++){
        int start = getParent(costs[i][0]);
        int end = getParent(costs[i][1]);
        int cost = costs[i][2];

        if(start != end){
            d[end] = start;

            answer += cost;
        }
    }


    return answer;
}

🧐 분석

1. 크루스칼 알고리즘과 Union-Find 알고리즘을 사용하고 있다.
2. 경로 최적화는 하고 있지만, Union by rank 최적화는 진행하고 있지 않다.
3. 전체적으로 내가 짠 코드와 동일하다.

🪶 후기

이 문제를 보자말자 크루스칼 알고리즘을 써야한다는 것이 떠올랐다.
하지만 간선을 추가했을때 사이클 발생 여부를 확인하는 방법이 기억이 안나, 1시간을 초과해버렸다.

어떠한 알고리즘이 있는지 알고, 구현할수 있는 능력을 갖추는 것이 중요할 것이다.

Programmers 카테고리 내 다른 글 보러가기