문제링크

틀린 풀이

0번 섬에서 시작하여 모든 섬을 한번씩 방문하는 최소 비용을 찾는 로직이라 틀림

#include <vector>
#include <unordered_map>

using namespace std;
struct bridge
{
    int island;
    int cost;
};
void dfs(unordered_map<int, vector<bridge>>& myMap, vector<bool>& visited, int visitedCount, int island, int cost, int& minCost)
{
    if(visitedCount == visited.size())
    {
        minCost = minCost<cost? minCost : cost;
        return;
    }
    for(const auto& m:myMap[island])
    {
        if(visited[m.island]) continue;
        visited[m.island] = true;
        dfs(myMap, visited, visitedCount+1, m.island, cost+m.cost, minCost);
        visited[m.island] = false;
    }
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 1e9;
    unordered_map<int, vector<bridge>> myMap;
    for(auto& v:costs)
    {
        myMap[v[0]].push_back({v[1], v[2]});
        myMap[v[1]].push_back({v[0], v[2]});
    }
    vector<bool> visited(n,false);
    visited[0] = true;
    dfs(myMap, visited, 1, 0, 0, answer);
    return answer;
}

최종 - Kruskal(Union-Find)

최소 신장 트리(MST)의 개념으로 접근하여 해결했다.
최소 신장 트리: 모든 노드를 연결하며 사이클이 없는 부분 그래프(신장 트리) 중 가중치의 합이 최소가 되는 트리

#include <vector>
#include <algorithm>

using namespace std;

int parent[100];

int find(int x)
{
    // 경로 압축
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unite(int a, int b)
{
    a = find(a);
    b = find(b);
    parent[a] = b;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    // parent 초기화
    for(int i=0; i<n; i++)
    {
        parent[i] = i;
    }
    
    sort(costs.begin(), costs.end(),
        [](const auto& a, const auto& b)
         {
             return a[2]<b[2];
         });
    int edgeCount = 0;
    for(const auto& cost:costs)
    {
        int from = cost[0];
        int to = cost[1];
        int weight = cost[2];
        
        // 최상위 부모가 같지 않으면 선택
        if(find(from)!=find(to))
        {
            unite(from, to);
            answer += weight;
            ++edgeCount;
            
            // n-1개의 간선을 선택하면 종료
            if(edgeCount == n-1)
            {
                break;
            }
        }
    }
    return answer;
}

최소 신장 트리(MST) 찾는 기법

Union - Find

개념

서로소 집합(Disjoint Set)을 표현하는 자료구조. "두 원소가 같은 집합에 속하는지" 빠르게 판단하고, 두 집합을 합칠 수 있음.

핵심 연산

1. Find: 원소가 속한 집합의 대표(루트) 찾기
2. Union: 두 집합을 하나로 합치기

구현

int parent[MAX];

// 초기화: 각자가 자신의 부모
for(int i = 0; i < n; i++)
    parent[i] = i;

// Find: 루트 찾기 + 경로 압축
int find(int x) {
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);  // 경로 압축
}

// Union: 두 집합 합치기
void union(int a, int b) {
    a = find(a);
    b = find(b);
    if(a != b) parent[a] = b;
}

// 같은 집합인지 확인
if(find(a) == find(b)) // 같은 집합

경로 압축 (Path Compression)

return parent[x] = find(parent[x]);

• find 호출 시 경로상 모든 노드를 루트에 직접 연결
• 트리 높이를 줄여 다음 find를 O(1)로 만듦

시간 복잡도

• 경로 압축 사용 시: O(α(n)) ≈ O(1) (아커만 역함수, 실질적 상수)
• 경로 압축 없으면: O(n)

활용

• 최소 신장 트리(MST): Kruskal 알고리즘에서 사이클 검사
• 네트워크 연결성: 두 노드가 연결되어 있는지 판단
• 동적 연결성: 간선 추가하면서 실시간으로 연결 여부 확인

Kruskal에서의 역할

sort(edges);  // 간선을 비용순 정렬
for(간선 in edges) {
    if(find(u) != find(v)) {  // 사이클 안 생기면
        union(u, v);           // 연결
        answer += cost;
    }
}

핵심: Union-Find로 "이 간선을 추가하면 사이클이 생기는가?"를 O(1)에 판단한다.

Kruskal 알고리즘

Kruskal = Union-Find + 그리디

Union-Find: "사이클 검사 도구"
     +
그리디: "비용이 작은 간선부터 선택하는 전략"
     =
Kruskal 알고리즘

알고리즘 순서

// 1. 간선을 비용 기준 오름차순 정렬 ⭐ (그리디)
sort(edges, 비용순);

// 2. 작은 비용부터 하나씩 확인
for(간선 in edges) {
    // 3. Union-Find로 사이클 체크
    if(find(u) != find(v)) {  // 다른 집합이면
        union(u, v);           // 합치기
        answer += cost;
        edgeCount++;
        
        // 4. n-1개 선택하면 완료
        if(edgeCount == n-1) break;
    }
}

핵심 아이디어

요소	역할
정렬 (그리디)	비용 작은 간선부터 고려
Union-Find	사이클 안 생기는지 체크
n-1개 선택	트리는 n개 노드에 n-1개 간선

왜 이게 최소 신장 트리?

1. 비용이 작은 것부터 선택 (그리디)
2. 사이클만 안 만들면 무조건 선택
3. 결과적으로 최소 비용으로 모든 노드 연결

시간 복잡도

• 정렬: O(E log E)
• Union-Find: O(E α(V)) ≈ O(E)
• 전체: O(E log E) (정렬이 지배)

정리: Kruskal은 Union-Find를 사이클 체크 도구로 사용하면서, "비용 작은 간선부터 선택"이라는 그리디 전략을 추가한 MST 알고리즘

Prim 알고리즘

Kruskal vs Prim 핵심 차이

	Kruskal	Prim
접근	간선 중심	정점 중심
방식	모든 간선 정렬 후 선택	한 정점에서 시작해 확장
자료구조	Union-Find	우선순위 큐
느낌	정렬 + 그리디	BFS의 변형

알고리즘 순서

// 1. 시작 정점 선택 (보통 0번)
visited[0] = true;

// 2. 시작 정점의 모든 간선을 우선순위 큐에 추가
for(간선 in graph[0])
    pq.push(간선);

// 3. 비용 작은 간선부터 꺼내기
while(!pq.empty()) {
    edge = pq.top(); pq.pop();
    
    // 이미 방문한 정점이면 스킵
    if(visited[edge.to]) continue;
    
    // 새 정점 연결
    visited[edge.to] = true;
    answer += edge.cost;
    
    // 새로 연결된 정점의 간선들 추가
    for(간선 in graph[edge.to])
        if(!visited[간선.to])
            pq.push(간선);
}

핵심 아이디어

"현재 트리에 연결 가능한 간선 중 가장 비용이 작은 것 선택"

• 트리를 점진적으로 확장
• 항상 연결된 상태 유지
• 우선순위 큐로 최소 비용 간선 선택

시각화

Kruskal (간선 관점):
모든 간선 보고 → 작은 것부터 선택 → 사이클만 피하기

Prim (정점 관점):
시작점 → 인접 정점 중 가장 가까운 곳 → 계속 확장

시간 복잡도

• 우선순위 큐: O(E log E)
• 전체: O(E log E) 또는 O(E log V)

언제 뭘 쓸까?

상황	추천 알고리즘
간선이 정렬되어 있음	Kruskal
간선 수가 적음 (희소 그래프)	Kruskal
간선 수가 많음 (밀집 그래프)	Prim
특정 정점에서 시작	Prim

둘 다 정확도와 시간복잡도는 같다. 구현 편의나 그래프 특성에 따라 선택.