Python, C, C++로 그리디(Greedy) 알고리즘(Minimum Spanning Tree) 쉽게 배우기

5. 그리디 (Greedy)

매 단계에서 “당장 최선”을 고르면 전체도 최적이 되는 구조에서 유효하다.

• 동전 거스름돈 – 특정 화폐 체계에서 최소 동전 수 산출 GeeksforGeeks
• Minimum Spanning Tree – “모든 지점을 반드시 잇되, 공사비나 거리 같은 가중치를 최소화”해야 하는 문제라면 거의 다 MST가 바탕 설계도야. Kruskal·Prim 모두 매번 최소 간선 선택 (O(E log E)) GeeksforGeeks  

Python Code

(1) 크루스칼: 간선 정렬 + 유니온 파인드

# kruskal_mst.py
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: 
            return False
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        elif self.rank[ra] > self.rank[rb]:
            self.parent[rb] = ra
        else:
            self.parent[rb] = ra
            self.rank[ra] += 1
        return True

def kruskal(n, edges):
    """edges: (w,u,v) 튜플 리스트, 정점은 0~n-1"""
    uf = UnionFind(n)
    mst, total = [], 0
    for w, u, v in sorted(edges):              # 가중치 오름차순
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n-1: break
    return total, mst

if __name__ == "__main__":
    N = 4
    E = [(1,0,1),(3,0,2),(4,0,3),(2,1,2),(5,2,3)]
    cost, tree = kruskal(N, E)
    print("MST cost:", cost)
    print("edges :", tree)

 

(2) 프림: 우선순위 큐(서로 다른 그래프 형태에 강함)

# prim_mst.py
import heapq
from collections import defaultdict

def prim(n, adj, start=0):
    """adj: {u:[(w,v),…]} 형태 인접 리스트"""
    visited = [False]*n
    h = [(0, start, -1)]          # (가중치, 현재정점, 부모)
    mst, total = [], 0

    while h and len(mst) < n-1:
        w, u, p = heapq.heappop(h)
        if visited[u]: 
            continue
        visited[u] = True
        if p != -1:               # 시작점 제외
            mst.append((p, u, w))
            total += w
        for w2, v in adj[u]:
            if not visited[v]:
                heapq.heappush(h, (w2, v, u))
    return total, mst

if __name__ == "__main__":
    N = 5
    adj = defaultdict(list)
    edges = [(1,0,1),(4,0,2),(3,1,2),(2,1,3),(5,2,3),(7,2,4),(6,3,4)]
    for w,u,v in edges:
        adj[u].append((w,v))
        adj[v].append((w,u))
    cost, tree = prim(N, adj)
    print("MST cost:", cost)
    print("edges :", tree)

---

C Code

(1)  Kruskal (간선 정렬 + 유니온-파인드)

/* kruskal_mst.c */
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int u, v, w;          /* 양 끝 정점, 가중치 */
} Edge;

/* ---------- 유니온-파인드 ---------- */
int find(int parent[], int x) {
    return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
int unite(int parent[], int rank[], int a, int b) {
    a = find(parent, a);
    b = find(parent, b);
    if (a == b) return 0;            /* 이미 같은 집합 → 간선 제외 */
    if (rank[a] < rank[b]) parent[a] = b;
    else if (rank[a] > rank[b]) parent[b] = a;
    else { parent[b] = a; rank[a]++; }
    return 1;                        /* 간선 채택 */
}

/* ----------- 메인 루틴 ----------- */
int cmp_edge(const void *a, const void *b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}
int main(void) {
    /* ===== 예시 그래프 ===== */
    int n = 4;   /* 정점 개수(0~3)        */
    Edge edges[] = { {0,1,1},{0,2,3},{0,3,4},{1,2,2},{2,3,5} };
    int m = sizeof(edges)/sizeof(edges[0]);

    /* 1. 간선 가중치 기준 정렬 */
    qsort(edges, m, sizeof(Edge), cmp_edge);

    /* 2. 유니온-파인드 초기화 */
    int *parent = malloc(n * sizeof(int));
    int *rank   = calloc(n, sizeof(int));
    for (int i = 0; i < n; ++i) parent[i] = i;

    /* 3. 간선 순회하며 MST 구성 */
    int picked = 0, total = 0;
    printf("MST edges:\n");
    for (int i = 0; i < m && picked < n-1; ++i) {
        if (unite(parent, rank, edges[i].u, edges[i].v)) {
            printf("  %d - %d (w=%d)\n", edges[i].u, edges[i].v, edges[i].w);
            total += edges[i].w;
            picked++;
        }
    }
    printf("MST cost = %d\n", total);

    free(parent); free(rank);
    return 0;
}

(2) Prim (인접 리스트 + 최소 힙)

/* prim_mst.c */
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define VMAX 10          /* 최대 정점 수 (간단히 고정) */
#define INF  INT_MAX

int main(void) {
    int n = 5;           /* 정점 개수 0~4 */

    /* 인접 행렬 (가중치) — 없으면 INF */
    int g[VMAX][VMAX] = {
        {0, 1, 4, INF, INF},
        {1, 0, 3, 2, INF},
        {4, 3, 0, 5, 7},
        {INF, 2, 5, 0, 6},
        {INF, INF, 7, 6, 0}
    };

    /* Prim 초기 설정 */
    bool inMST[VMAX] = {false};
    int  key[VMAX];          /* 각 정점까지의 최소 비용 */
    int  parent[VMAX];       /* MST에서의 부모 정점   */
    for (int i = 0; i < n; ++i) {
        key[i] = INF;
        parent[i] = -1;
    }
    key[0] = 0;              /* 시작 정점은 0 */

    /* 정점 n개 중 n-1번 선택 */
    for (int step = 0; step < n-1; ++step) {

        /* 1. MST 바깥에서 key가 가장 작은 정점 u 찾기 */
        int u = -1, minKey = INF;
        for (int v = 0; v < n; ++v)
            if (!inMST[v] && key[v] < minKey) {
                minKey = key[v];
                u = v;
            }
        inMST[u] = true;

        /* 2. u에 인접한 정점의 key 값 갱신 */
        for (int v = 0; v < n; ++v) {
            if (g[u][v] != INF && !inMST[v] && g[u][v] < key[v]) {
                key[v] = g[u][v];
                parent[v] = u;
            }
        }
    }

    /* 결과 출력 */
    int total = 0;
    printf("MST edges:\n");
    for (int v = 1; v < n; ++v) {
        printf("  %d - %d (w=%d)\n", parent[v], v, g[v][parent[v]]);
        total += g[v][parent[v]];
    }
    printf("MST cost = %d\n", total);
    return 0;
}

---

C++ Code

(1) 크루스칼

// kruskal_mst.cpp
#include <bits/stdc++.h>
using namespace std;

struct Edge {int w, u, v;};
struct DSU {
    vector<int> p, r;
    DSU(int n): p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;
        if(r[a]<r[b]) swap(a,b);
        p[b]=a;
        if(r[a]==r[b]) r[a]++;
        return true;
    }
};

int main(){
    int n=4;
    vector<Edge> e={{1,0,1},{3,0,2},{4,0,3},{2,1,2},{5,2,3}};
    sort(e.begin(), e.end(), [](auto &a,auto &b){return a.w<b.w;});
    DSU dsu(n);
    long long total=0;
    vector<Edge> mst;
    for(auto &ed:e){
        if(dsu.unite(ed.u, ed.v)){
            mst.push_back(ed);
            total += ed.w;
            if(mst.size()==n-1) break;
        }
    }
    cout<<"MST cost: "<<total<<"\n";
    for(auto &ed:mst) cout<<ed.u<<"-"<<ed.v<<" ("<<ed.w<<")\n";
}

 

(2) 프림

// prim_mst.cpp
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;        // (w, v)

int main(){
    int n=5;
    vector<vector<pii>> adj(n);
    vector<tuple<int,int,int>> edges={{1,0,1},{4,0,2},{3,1,2},
                                      {2,1,3},{5,2,3},{7,2,4},{6,3,4}};
    for(auto [w,u,v]:edges){
        adj[u].push_back({w,v});
        adj[v].push_back({w,u});
    }

    vector<int> parent(n,-1), key(n,INT_MAX);
    vector<bool> inMST(n,false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0,0}); key[0]=0;

    while(!pq.empty()){
        auto [w,u]=pq.top(); pq.pop();
        if(inMST[u]) continue;
        inMST[u]=true;
        for(auto [wt,v]:adj[u]){
            if(!inMST[v] && wt<key[v]){
                key[v]=wt; parent[v]=u;
                pq.push({key[v], v});
            }
        }
    }

    long long total=0;
    for(int v=1; v<n; ++v){
        cout<<parent[v]<<"-"<<v<<" ("<<key[v]<<")\n";
        total += key[v];
    }
    cout<<"MST cost: "<<total<<"\n";
}

---

결과값

1. #크루스칼
2. MST cost: 7
3. edges : [(0, 1, 1), (1, 2, 2), (0, 3, 4)]
4. #프림
5. MST cost: 12
6. edges : [(0, 1, 1), (1, 3, 2), (1, 2, 3), (3, 4, 6)]

0. 입력 세팅

정점	좌표 (x, y)
0	(0.0, 0.0)
1	(1.0, 1.2)
2	(2.0, 0.0)
3	(0.5, -0.6)
4	(1.5, -0.6)

 

그래프를 쉽게 그리고 싶어서 2-D 좌표를 직접 줬어.
두 정점 u,vu,vu,v 사이 거리(=가중치)는 유클리드 거리

 

​

를 math.hypot으로 계산했지.

 

1. 간선 하나씩 스캔하면서 MST 구축

스텝	간선 (u,v,w)	서로 다른 집합?	선택 여부	parent/ rank 변화	MST 간선 수
①	(0-1, 1.562)	✔️	✔️ 추가	0←1 합침	1
②	(2-4, 0.632)	✔️	✔️ 추가	2←4 합침	2
③	(0-3, 0.721)	✔️	✔️ 추가	0←3 합침	3
④	(1-2, 1.118)	✔️	✔️ 추가	0←2 트리 결합	4 (= n-1) → 종료
그 밖	나머지 6개	✖️ or 더 볼 필요 없음	-	-	-

 

규칙

1. 간선을 가벼운 순서로 본다.
2. 그 간선의 양 끝 정점이 다른 집합이면 ⇒ 싸이클이 안 생기니까 채택.
3. 채택했으면 두 집합을 union()으로 합친다.
4. n−1n-1n−1개가 되면 끝.

 

분야	구체적 사용 사례	왜 MST가 맞춤형 해법인지
1. 통신·전력 같은 인프라 네트워크 설계	- 전화선·광섬유·전력선·수도관을 여러 거점에 “최소 공사비”로 잇기- 통신사 백본망(POP 간 링크) 초기 배선도 작성	네트워크는 ‘연결 + 비용 최소’가 핵심이므로 “싸이클 없이 전 정점을 가볍게 묶는” MST가 바로 최적 모델. 실제 계획-수치에 MST를 얹어 비용을 산출한 연구가 다수 있음. (personal.utdallas.edu, geeksforgeeks.org, library.fiveable.me)
2. 교통·도시 인프라/물류	- 신규 도로·철도 노선을 최소 공사거리로 설계- 항만·공항 간 연계 파이프라인·컨베이어 라우팅	복수 시설을 전부 연결해야 하는 스패닝 문제가 기본 구조. 최근 교통 인프라 편익 분석 논문에서도 MST 기반 모델로 노선을 스케치한 뒤 추가 제약을 얹어 시뮬레이션함. (journals.sagepub.com)
3. 전자회로·PCB·칩 배선	- IC 내부 전력/클럭 트리 배선 길이를 줄여 지연·소모 전력↓- 대형 PCB에서 여러 커넥터를 한 번에 묶는 “rat-nest” 정리	배선 길이가 바로 원가·신호 지연으로 직결되기 때문에, 선을 최소화하며 모든 핀을 연결하는 MST를 초벌 배치로 씀. 이후 전기적 제약(층수·임피던스 등)을 추가 조정. (geeksforgeeks.org)
4. 데이터 과학·머신러닝	- 단일 연결(싱글-링크) 계층적 클러스터링: 전체 데이터로 완전 그래프를 만든 뒤 MST에서 가장 긴 k−1k-1 간선을 끊어 kk 개 군집 획득- 고차원 특성선택·이상치 탐지	MST는 경계가 희박한 영역을 자연스럽게 잘라 주므로 거리 기반 군집·이상치 탐지에 빠르고 직관적. 최신 연구에서도 “MST가 저차원 데이터엔 경쟁력 있음” 결과 확인. (cs.cmu.edu, link.springer.com, en.wikipedia.org)
5. 영상 처리·컴퓨터 비전	- 그래프 기반 영상 분할(Felzenszwalb-Huttenlocher 등): 픽셀을 노드, 색거리/경계값을 가중치로 두고 MST를 따라 영역을 병합- 의료 영상(CT, MRI) 구조 분리	픽셀/슈퍼픽셀을 가장 “자연스러운 내부 유사도” 순서로 잇는 MST가, 영역 경계(가장 무거운 간선)만 잘 끊어주면 의미 있는 분할을 준다.(sciencedirect.com, journals.sagepub.com)
6. 그래프-기반 최적화 알고리즘의 재료	- Christofides TSP 근사: MST → 최소 완전 매칭 → Euler 순회를 압축해 1.5-근사 경로 생성- Steiner Tree 근사: MST로 상한선 마련 후 후보 간선 축소	복잡한 문제를 “MST + 후처리”로 푼 뒤 근사보장 분석을 붙이기 쉽다. 교과서·산업용 솔버 둘 다 즐겨 쓰는 기법. (kafaby.medium.com)
7. 로봇·게임· GIS 경로 계획	- 넓은 지형에서 자율주행 Waypoint를 ‘뼈대’ 형태로 잇기- 도시 GIS에서 가상 길찾기 베이스라인 구축	일단 MST로 전체를 묶어두면, 이후 A*·다익스트라 탐색 범위가 크게 줄어 속도 향상. (community.esri.com)
8. 교육·인터뷰·문제 출제	- 컴공 알고리즘 강의에서 “최적 vs 그리디 예시”로 단골- 코딩 테스트에서 Kruskal/Prim 구현, ‘도로 건설 최소 비용’ 유형	이론·구현·증명이 모두 깔끔해 학습용 예제로 최적. (library.fiveable.me)