[DAY92] Algorithm : Island Connect

섬 사이에 다리를 놓는 비용이 주어졌을 때, 모든 섬을 통행 가능하게 만드는 최소 비용을 구하는 문제다. 최소 신장 트리(MST)를 구하는 대표적인 문제로, 비용이 낮은 간선부터 선택하는 그리디(Greedy) 방식과 사이클 생성을 막기 위한 유니온-파인드(Union-Find) 알고리즘을 결합한 크루스칼 알고리즘을 사용해야 한다.

---

❓ 문제 분석

• 목표: 모든 섬(노드)을 연결하는 다리(간선) 건설 비용의 최솟값 구하기.
• 제약 조건:
  • 섬의 개수 $N$: 최대 100 / 비용 배열 costs의 길이: 최대 약 5,000
  • 모든 섬이 연결되어야 하며, 불필요한(비싼) 다리는 짓지 않아야 한다.
• 핵심 키워드: "최소의 비용", "모든 섬 통행 가능", "연결(Connection)"

---

💡 풀이 설계

1. 시도했던 접근 (Intuition)

• 모든 섬을 연결해야 하니, 단순히 눈앞에 보이는 싼 다리부터 무작정 연결하면 되지 않을까 생각했다.
• 하지만 무작정 연결하다 보면, 이미 연결된 두 섬 사이에 또 다리를 놓는 낭비가 발생할 수 있다. 이를 걸러내는 장치가 필요하다.

2. 최종 해결책 (Kruskal's Algorithm)

• 전략: 가장 적은 비용으로 모든 노드를 연결하는 최소 신장 트리(MST)를 만든다.
• 핵심 로직:
  1. 정렬: 다리 건설 비용을 기준으로 오름차순 정렬한다. (싼 것부터 검토)
  2. 선택: 가장 싼 다리를 꺼낸다.
  3. 검증(Cycle Check): 이 다리가 연결하려는 두 섬이 이미 연결되어 있는지 확인한다.
     • 이미 연결된 상태라면? $\rightarrow$ 짓지 않고 넘어간다. (Cycle 방지)
     • 연결되지 않은 상태라면? $\rightarrow$ 건설하고 비용을 추가한다.
• 자료구조: 두 섬의 연결 여부(같은 집합인지)를 효율적으로 확인하기 위해 유니온-파인드(Union-Find) 알고리즘을 사용한다.
• 예상 시간 복잡도: $O(E \log E)$
  • 간선을 정렬하는 시간이 가장 오래 걸리므로, 간선 개수($E$)에 비례한다.

---

💻 코드 구현

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

using namespace std;

// [Union-Find] 부모 노드(Root)를 찾는 함수 (경로 압축 최적화 포함)
int getParent(vector<int>& parent, int x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

// [Union-Find] 두 노드를 하나의 집합으로 합치는 함수
void unionParent(vector<int>& parent, int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 부모 테이블 초기화 : 모든 섬이 각자 독립된 상태로 시작
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    // 간선을 비용(cost) 기준으로 오름차순 정렬
    // 람다 함수를 이용해 2번 인덱스(비용)를 비교
    sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
    });
    
    // 간선을 하나씩 확인하며 크루스칼 알고리즘 수행
    for (auto& edge : costs) {
        int islandA = edge[0];
        int islandB = edge[1];
        int cost = edge[2];
        
        // 두 섬의 부모가 다르면(연결되어 있지 않으면) -> 연결하고 비용 추가
        if (getParent(parent, islandA) != getParent(parent, islandB)) {
            unionParent(parent, islandA, islandB);
            answer += cost;
        }
    }
    
    return answer;
}

---

🐛 시행착오 및 디버깅

• 정렬 기준: 처음엔 sort를 어떻게 써야 할지 막막했으나, costs가 2차원 벡터이므로 람다 함수(Lambda)를 사용해 edge[2](비용)를 기준으로 정렬하도록 구현했다.
• 사이클 판단: 단순히 방문 여부(visited)만으로는 두 섬이 같은 네트워크에 있는지 확인하기 어렵다. 그래서 부모 노드를 확인하는 getParent 함수를 구현하여 해결했다.

---

✅ 오늘의 회고

항목	내용
유형	그리디 (Greedy), 그래프 (Graph), 최소 신장 트리 (MST)
체감 난이도	상 (개념을 모르면 풀기 어려움)
복잡도	시간: $O(E \log E)$ (정렬 시간)
새로 배운 것	크루스칼 알고리즘의 전체 흐름과, 이를 구현하기 위한 도구인 유니온-파인드(Union-Find) 자료구조의 구현법을 익혔다.