문제 조건

input

• 섬의 개수 n
  • 1 ≤ n ≤ 100
• 섬의 연결 비용
  • 1 ≤ costs.len ≤ ((n-1) * n) / 2

output

• 최소 건설 비용

문제 해석

1. 단순 구현

   1. costs 정렬(비용을 기준으로 오름차순)
   2. costs 순회
      1. set을 만들고, set에 섬이 포함되어 있다면 pass
      2. 아닐 경우, 건설하고 건설 비용 추가
      3. set에 모든 섬이 다 들어오면 break

   —> 일부 케이스만 통과

2. 크루스칼

   1. 최소 신장 트리
      1. 신장 트리이면서 정점간의 가중치가 최소인 것
      2. 신장 트리: 그래프 내 모든 정점을 포함하는 트리/ 사이클이 없어야함
   2. 사이클 판별
      1. 배열 선언 set[i] = i
      2. set[e] = s → e의 parent는 s이다.
      3. set[i] = i이면 부모까지 왔음
      4. 건설하려고 하는 두 지점의 부모가 같다면 → 사이클 발생

코드

1. 단순 구현

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

using namespace std;

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

int solution(int n, vector<vector<int>> costs) {
    // cost[i][0] <-> cost[i][1] 두 섬을 연결할 때, cost[i][2]의 비용이 발생
    
    // sorting 실행
    sort(costs.begin(), costs.end(), compare);
    set<int> islands; 
    int answer = 0;
    
    // for문 순회 costs만큼
    for (auto cost : costs) {
        // islands set에 추가
            // cost[0]
            // cost[1]
        islands.insert(cost[0]);
        islands.insert(cost[1]);
    
        // 건설 비용에 cost[2]
        answer += cost[2];
        
        // 만약, islands set의 개수가 n-1개이면
            //바로 탈출
        if (islands.size() == n) break;
    }
    
    return answer;
}

1. 최소 신장 트리

#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
int set[101];   // node의 parent를 저장하는 배열
 
// node의 parent를 리턴하는 함수
int getParent(int node) {
    if(set[node] == node) return node;
    return set[node] = getParent(set[node]);
}
 
bool cmp(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++)
        set[i] = i;
    
    sort(costs.begin(), costs.end(), cmp);  // 비용을 오름차순 정렬
 
    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) {  // cycle이 만들어지지 않을 경우 다리를 추가
            answer += cost;
            set[end] = start;
        }
    }
 
    return answer;
}