yg log --graph --oneline --all

Home Stack Notes AboutRSS

12. 가장 싼 선택을 믿을 수 있는 조건

작성 · 6분 읽기 · 조회수 —수정

기초 개념과 예제를 보강하고 시리즈 흐름을 연결

모든 정점을 가장 싸게 잇는 문제

입력은 연결된 무방향 그래프와 각 간선의 비용이다. 원하는 답은 모든 정점을 사이클 없이 연결하면서 총비용이 가장 작은 간선 집합이다.

정점: 0, 1, 2
간선: 0-1(1), 1-2(2), 0-2(5)
답: 0-1과 1-2, 총비용 3

원래 그래프의 모든 정점을 포함하고 일부 간선을 고른 그래프를 신장 부분그래프라고 한다. 신장 부분그래프라는 말만으로는 연결되어 있다는 뜻이 아니다. 모든 정점을 포함하면서 연결되어 있고 사이클도 없는 신장 부분그래프가 신장트리(spanning tree)다. 정점이 $V$개인 신장트리는 간선이 정확히 $V-1$개다. 가능한 신장트리 중 가중치 합이 최소인 것을 최소신장트리(MST)라고 한다.

따라서 사이클이 없다는 것은 비용의 부수적인 결과가 아니라 답으로 허용되는 트리의 조건이다. 이 정의는 음수 간선이 있어도 그대로 적용된다. 음수 간선을 더 넣으면 총비용이 작아질 수 있지만, 사이클을 만든 순간 그 간선 집합은 신장트리가 아니므로 MST 후보에서 제외된다.

MST와 최단 경로는 모두 작은 가중치를 찾지만 답의 모양이 다르다.

문제 입력에서 추가로 정하는 것 최소화하는 값 답
MST 출발점이 필요 없음 선택한 트리 간선 전체의 합 모든 정점을 잇는 트리
단일 출발 최단 경로 출발점 하나 출발점에서 각 정점까지의 경로 비용 정점별 거리와 경로

위 구분을 먼저 잡아 두면 뒤에서 Prim의 key와 Dijkstra의 dist가 비슷한 코드 모양인데도 다른 값을 저장하는 이유가 보인다.

당연하다고 적은 선택의 근거

최소신장트리 노트에서 분할을 가로지르는 최소 무게 간선을 포함하는 MST가 존재한다는 문장 아래에 “당연하지!”라고 적었다. 조금 아래에는 동전 예시를 길게 덧붙였다.

다른 예시로 동전이 30원, 20원, 5원, 1원 인경우 40원을 거슬러 줄 때 탐욕적 선택 속성을 적용하면 30원 5원 5원으로 동전 세 개인데 20원짜리로 거슬러 주면 20원 20원으로 동전 두 개이다.

가장 큰 동전을 먼저 고르면 늘 개수가 최소인 것은 아니다. 이 반례를 알고도 MST에서는 가장 싼 간선을 골라도 된다고 말한다. 두 문장을 나란히 놓으면 “당연하지” 뒤에 빠져 있던 설명이 드러난다. 지금 좋아 보이는 선택이 전체 최적해를 망치지 않는 근거가 필요하다.

노트의 동전 예시는 그 필요를 설명하는 출발점이다. 특정 금액 하나에서 탐욕법이 성공했다고 해서 모든 금액에서 성공함을 증명한 것은 아니지만, 단 하나의 반례는 무조건적인 주장을 깨뜨린다. MST에서는 반례를 피하는 조건을 분할 속성으로 설명할 수 있다.

싼 간선으로 바꾸어도 더 비싸지 않다

연결된 무방향 가중 그래프의 정점을 두 집합 S와 그 밖으로 나누자. 두 집합 사이를 가로지르는 간선 중 최소 무게인 것을 e라고 하자.

어떤 MST T가 e를 이미 포함하면 문제가 없다. 포함하지 않는다면 e를 T에 추가해 보자. 트리의 두 정점 사이에는 경로가 하나씩 있으므로 순환이 하나 생긴다. 그 순환에는 e 말고도 두 집합 사이를 가로지르는 간선 f가 있다. e는 그 분할의 최소이므로 weight(e) ≤ weight(f)다.

f를 빼고 e를 남기면 다시 신장트리가 되고, 총 무게는 증가하지 않는다. T가 이미 최소였으니 새 트리도 MST다. 그래서 e를 포함하는 MST가 적어도 하나 존재한다고 말할 수 있다. 이것이 작은 값을 고르는 직감 뒤의 교환 논증이다. Algorithms, 4th Edition의 분할 속성과 탐욕적 MST 구성

동률인 간선이 있을 때 e가 모든 MST에 반드시 들어간다는 뜻은 아니다. 또 여러 간선을 쌓아 갈 때는 이미 선택한 간선을 가로지르지 않는 분할을 골라야 기존 선택과 함께 유지할 수 있다. Prim과 Kruskal은 그 조건을 각기 다른 방식으로 만든다.

Prim은 지금 만든 나무의 경계를 본다

다음 다섯 간선을 가진 네 정점 그래프를 새 예제로 사용했다.

0--1: 1
0--2: 4
1--2: 2
1--3: 5
2--3: 3

0에서 시작하는 Prim의 진행은 다음과 같다.

현재 나무의 정점 밖으로 이어지는 후보 선택
{0} 0–1: 1, 0–2: 4 0–1
{0,1} 0–2: 4, 1–2: 2, 1–3: 5 1–2
{0,1,2} 1–3: 5, 2–3: 3 2–3

총 무게는 6이다. 노트에서 d(v)를 “배낭 안의 정점과 배낭 밖의 정점을 연결하는 간선의 무게”라고 적은 부분이 여기서 중요하다. 아래 코드의 key[v]도 현재 나무에 v를 붙이는 간선 하나의 최솟값이다.

for (Node *p = g->adj[u]; p; p = p->next) {
    if (!used[p->vertex] && p->weight < key[p->vertex]) {
        key[p->vertex] = p->weight;
    }
}

시작점에서 v까지 지나온 가중치를 모두 더하는 값이 아니다. 마지막 단계의 key[3]은 3이고, 만들어진 트리에서 0→1→2→3의 경로 합은 6이다. 다음 글의 최단 경로와 코드가 비슷해 보여도 저장하는 값부터 다르다.

이번 구현은 다음 정점을 고를 때 미사용 정점을 전부 검사한다. 따라서 Prim의 시간은 O(V²+E), 단순 그래프에서는 O(V²)다. 노트에 적힌 O(E log V)는 연결 그래프에서 힙을 사용하는 구현의 분석이다. 배열로 최솟값을 고르는 코드에 힙의 복잡도를 붙이면 안 된다.

Kruskal은 서로 다른 나무를 잇는다

Kruskal은 시작 정점 대신 간선을 무게순으로 본다. 처음에는 각 정점이 별도 집합이다. 간선의 양끝이 서로 다른 집합이면 연결하고, 같은 집합이면 이미 경로가 있으므로 그 간선을 넣었을 때 순환이 생긴다.

static long long kruskal_forest(const Graph *g, int *components) {
    Edge edges[MAX_EDGES]; int m = edge_array(g, edges, true);
    qsort(edges, (size_t)m, sizeof edges[0], edge_compare);
    int parent[N], size[N];
    for (int v = 0; v < g->n; ++v) { parent[v] = v; size[v] = 1; }
    long long total = 0; *components = g->n;
    for (int i = 0; i < m; ++i)
        if (join(parent, size, edges[i].u, edges[i].v)) { total += edges[i].w; --*components; }
    return total;
}

join은 경로 압축과 크기 기준 병합을 사용하는 분리 집합 연산이다. 실제로 두 집합을 합친 경우에만 참을 반환하므로, 그때만 총 무게를 더한다. 예시에서는 무게 1, 2, 3의 간선을 선택해 6을 얻는다. 뒤에 남은 0–2와 1–3은 같은 집합 안의 정점을 잇기 때문에 선택하지 않는다.

현재 한 집합과 나머지를 나누면, 이번에 선택하는 간선은 그 분할을 가로지르는 가장 싼 간선 중 하나다. 이미 무게순으로 검사했고 더 싼 연결 후보를 지나쳤다면 그때 두 집합은 합쳐졌을 것이기 때문이다. 정렬이 O(E log E), 분리 집합 처리가 거의 선형이므로 전체는 정점 초기화를 포함해 O(V+E log E)로 볼 수 있다.

연결되지 않은 입력에서 반환할 답

연결되지 않은 그래프에는 모든 정점을 잇는 신장트리가 없다. 이번 함수 이름을 prim_forest, kruskal_forest로 둔 이유다. 각 연결요소의 최소신장트리를 모은 숲의 무게와 요소 수를 반환한다. 요소 수가 1일 때만 전체 그래프의 MST라고 부른다.

새 검증에서는 네 정점 사이의 여섯 간선 자리마다 없음, -2, 0, 3 중 하나를 배정해 4,096개 그래프를 만들었다. 두 알고리즘의 숲 무게와 요소 수를 비교했다. 연결된 경우에는 간선 부분집합을 모두 열거해 얻은 최소 신장트리 무게와도 일치했다. 음수 가중치와 동률을 포함해 검사한 것은, MST에는 가중치가 음수라는 이유만으로 선택 원리가 무너지지 않기 때문이다.

“가장 싼 것을 고른다”만 남기면 동전 반례와 MST를 구분할 수 없다. 이제 남길 문장은 조금 더 길다. 기존 선택을 유지하는 분할에서 가장 싼 연결을 골라, 더 비싸지 않은 최적해로 교환할 수 있다. 노트의 “당연하지”를 그 이유까지 포함한 설명으로 바꾼 것이다.

기록과 실행 코드

관련 포스트