섬 연결하기

섬 연결하기

사용 언어: C++

문제 요약

• n개의 섬이 있고, 각 섬 사이를 연결하는 다리 건설 비용이 주어집니다.
• 목표: 모든 섬이 서로 통행 가능하도록 만들면서 총 비용을 최소화
• 조건:
  • 다리를 여러 번 건너도 통행 가능하면 됨
  • 같은 연결은 중복 없음
  • 연결할 수 없는 섬은 존재하지 않음

즉, 모든 섬을 최소 비용으로 연결하는 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다.

MST 문제 접근법

MST 문제를 해결하는 대표 알고리즘이 두 개 정도가 있는데

1. 크루스칼 알고리즘

2. 프림 알고리즘

여기서 어떤 알고리즘을 선택하냐? 간단하게 정리하면 간선 개수가 V, 정점 수가 E라 할 때 크루스칼 알고리즘은 시간복잡도가 O(ElogE)이다.

프림 알고리즘은 시간복잡도가 O(VlogV + ElogV)인데 간선이 정점보다 보통 많으므로 사실상 O(ElogV)다.

결론적으로

-> 간선이 많은 경우? : 프림

-> 정점이 많은 경우? : 크루스칼.

이번 문제는 사실 프림이나 크루스칼 둘 다 사용 가능하지만 간선 리스트 그대로 사용 가능하고, 간선 수도 n<=100으로 작고, 구현도 간단해서 그냥 크루스칼로 푸는 게 조금 더 간단하다.

크루스칼 요약

• 모든 간선을 가중치 기준 오름차순 정렬
• 가장 작은 간선부터 MST에 포함
• 사이클이 생기면 건너뛰기
• Union-Find로 사이클 여부 판단

Union-Find (핵심 함수)

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);
    if(a != b) parent[a] = b;
}

크루스칼 알고리즘 흐름

1. 간선 구조체 정의

struct Edge {
    int u, v, w;
};

2. 모든 간선을 오름차순 정리

sort(edges.begin(), edges.end(), [](Edge a, Edge b){return a.w < b.w;});

// 왜 sort를 하냐? 현재 선택 가능한 간선 중 최소 비용 선택 -> 그리디 전략

3. 작은 가중치 간선부터 MST에 포함

int MST_weight = 0;
for(auto e : edges)
{
    if(find(e.u) != find(e.v))
    {
        unite(e.u, e.v);
        MST_weight += e.w;
    }
}

MST 완성후 MST_weight 자체가 최소 비용

풀이1 (크루스칼)

크루스칼이나 프림 특성 상 현재 선택 가능한 간선 중 최소 비용을 선택해서, 아마 프로그래머스에서 해당 문제를 그리디로 분류한 것 같다.

#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 101;

int parent[MAX];

int find(int x)
{
    if(x == parent[x]) return x;
    
    return parent[x] = find(parent[x]);
}

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

struct Edge {
    int u, v ,w;
};

bool compareEdge(Edge a, Edge b) { return a.w < b.w; }

int solution(int n, vector<vector<int>> costs) 
{
    for(int i=1; i<=n; i++) parent[i] = i;
    
    vector<Edge> edges;
    
    for(vector<int> c : costs)
    {
        edges.push_back({c[0], c[1], c[2]});
    }
    
    sort(edges.begin(), edges.end(), [](Edge a, Edge b){ return a.w < b.w; });
    
    int MST_weight = 0;
    for(auto e : edges)
    {
        int u = e.u;
        int v = e.v;
        int w = e.w;
        
        if(find(u) != find(v))
        {
            unite(u, v);
            MST_weight += w;
        }
    }
    
    return MST_weight;
}

풀이2 (프림)

크루스칼만큼은 아니지만 간단하게 정리해놨다.

 

• 인접 리스트 구성
  • 각 섬마다 연결된 섬과 비용을 저장
• 프림 알고리즘 수행
  • 우선순위 큐를 사용하여 MST에 연결 가능한 가장 작은 비용 간선 선택
  • 선택한 노드를 MST 집합에 포함 (visited)
  • 새로 연결 가능한 노드들의 간선을 큐에 추가
• 총 비용 계산
  • MST에 포함된 간선 비용을 모두 합산 → 최소 비용

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int solution(int n, vector<vector<int>> costs) 
{
    vector<vector<pair<int,int>>> adj(n); // {연결된 노드, 비용}
    for(auto c : costs) 
    {
        int u = c[0], v = c[1], w = c[2];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<bool> visited(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    int total_cost = 0;

    // 0번 노드부터 시작
    pq.push({0, 0}); // {비용, 노드}

    while(!pq.empty()) 
    {
        int cost = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if(visited[u]) continue;
        visited[u] = true;
        total_cost += cost;

        for(auto [v, w] : adj[u]) 
        {
            if(!visited[v]) 
            {
                pq.push({w, v});
            }
        }
    }

    return total_cost;
}