도시 분할 계획

백준 1647

GOLD IV

문제 내용
해결 방안
풀이 코드

문제 내용

문제 링크

해결 방안

문제의 내용을 요약하면, 마을을 두 개의 연결되지 않은 마을로 분리하고자 할 때, 분리된 각 마을 안의 집들에 대해 같은 마을 안의 다른 집들과 하나 이상의 경로가 있도록 하는 길의 유지비의 최솟값을 구하는 문제이다. 우선 길을 최소한으로 하기 위해서는 각 집 사이에 두 개 이상의 경로가 있을 필요가 없다. 때문에 마을 안의 집들을 노드라고 한다면, 우리는 각 마을을 두 개의 스패닝 트리로 나누면 된다. 그 중에서도 길의 유지비의 최솟값을 찾는 문제이므로, 이 문제는 최소 스패닝 트리 문제이다. 이번 문제에서는 최소 스패닝 트리를 찾는 알고리즘 중 크루스칼 알고리즘을 사용하여 풀이하도록 한다.

먼저, 각 간선들을 입력받아 간선의 가중치(길의 유지비) 순으로 정렬해야 한다. 그리고 가장 작은 가중치의 간선부터 하나씩 꺼내어, 간선에 의해 연결된 노드가 이미 연결되어 있는지 확인한다. 이때, Union Find 알고리즘을 통해 두 노드의 최상위 노드를 확인한다. 만약 두 노드의 최상위 노드가 같다면, 이미 두 노드가 직간접적인 방법으로 이어져 있다는 것을 의미한다. 간선을 적용하면 사이클이 만들어지거나 임의의 노드로 가는 경로가 2개가 만들어지므로, 해당 간선은 무시한다. 반대로 두 노드의 최상위 노드가 다르다면, 두 노드의 최상위 노드를 하나로 통일하고 해당 간선을 적용한다. 본래라면 최소 스패닝 트리가 만들어질 때까지 반복해야 하지만, 본 문제에서는 2개의 스패닝 트리를 만들면 되므로 Union Find 알고리즘으로 얻어지는 전체 노드에 대한 최상위 노드가 2개가 될 때까지 반복한다. 반복이 끝나면 결과적으로 최소 스패닝 트리가 각 최상위 노드를 기준으로 2개 만들어지기 때문에, 반복하는 과정까지의 간선의 가중치를 합하면 문제에서 찾는 답이 나온다.

최소 스패닝 트리(Minimum Spanning Tree; MST)란?

최소 스패닝 트리(Minimum Spanning Tree; MST)는 최소 비용 신장 트리라고도 불리는 그래프의 일종이다. 그래프의 모든 정점에 대해 최소한으로 직간접적인 연결이 된 그래프, 즉 모든 노드들을 가장 적은 간선으로 연결한 그래프를 스패닝 트리 혹은 신장 트리라고 한다. 스패닝 트리는 모든 노드가 서로 직간접적으로 연결되어 있지만, 사이클이 존재하지 않아야 한다. 때문에, 스패닝 트리 안의 임의의 두 노드에 대한 경로는 반드시 하나만 존재하며, 스패닝 트리의 간선의 개수는 (노드의 총 개수 - 1)개이어야 한다. 모든 노드가 직간접적으로 연결된 그래프에 대해 간선을 일부 없애 스패닝 트리를 만드는 것이 가능한데, 만들 수 있는 모든 스패닝 트리 중에서 각 간선의 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리라고 하는 것이다. 스패닝 트리를 만들 수 있는 임의의 그래프에 대해 최소 스패닝 트리를 찾는 알고리즘에는 프림 알고리즘이나 크루스칼 알고리즘 등이 있지만, 본 문제에서는 크루스칼 알고리즘을 활용한 풀이를 소개하고자 한다.

크루스칼 알고리즘(Kruskal’s algorithm)이란?

임의의 그래프에 대한 최소 스패닝 트리를 찾기 위한 알고리즘으로, 최소 스패닝 트리가 만들어질 때까지 연결되지 않은 노드의 가중치가 가장 작은 간선을 최적해로 삼는 그리디 알고리즘이다.

크루스칼 알고리즘으로 최소 스패닝 트리를 찾는 과정은 다음과 같다.

그래프의 모든 간선들을 가중치에 대한 오름차순으로 정렬하고, 현재 그래프의 모든 간선을 지운다.

정렬된 간선들 중 가중치가 가장 작은 간선을 그래프에 적용하여 두 노드를 연결한다.

연결된 노드와 노드 사이에 사이클이 발생하는 지 판별하기 위해, Union Find를 사용하여 각 노드와 연결된 집합이 배반사건인지 확인한다.

만약 연결된 노드 내에서 사이클이 발생하면, 가장 최근에 연결했던 간선을 지운다.

2~3의 과정을 모든 간선에 대해 수행했거나, 연결된 간선의 개수가 (노드의 총 개수 - 1)이라면 중단한다.

스패닝 트리의 간선의 개수는 (노드의 총 개수 - 1)이므로, 위 과정의 결과가 간선의 개수가 해당 수치라면 스패닝 트리가 완성된 것으로 간주해도 된다. 만약 모든 간선에 대해 수행했음에도 연결된 간선의 개수가 (노드의 총 개수 - 1)보다 작다면, 임의의 노드에 대해 연결 가능한 노드가 없는 것이다.

풀이 코드

#include <iostream>
#include <queue>

using namespace std;
typedef pair<int, pair<int, int>> edge;

// Union-Find 알고리즘(최상위 노드 탐색)
int getRoot(vector<int> &parent, int node) {
    if(parent[node] == node) return node;
    parent[node] = getRoot(parent, parent[node]);
    return parent[node];
}

int main() {
    // 노드의 개수와 간선의 개수
    int n, m;
    cin >> n >> m;

    // 각 집들과 그 사이의 길의 유지비를 입력 및
    // 입력받은 정보를 길의 유지비에 대해 오름차순 정렬
    int a, b, c;
    priority_queue<edge, vector<edge>, greater<edge>> edges;
    for(int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        edges.push({c, {a, b}});
    }

    // 각 노드의 최상위 노드(루트 노드) 저장
    vector<int> parent(n + 1);
    for(int i = 0; i <= n; i++)
        parent[i] = i;
    
    // 최상위 노드의 개수
    int rootCount = n;
    // 최소 비용
    int cost = 0;
    
    // 최상위 노드의 개수가 2개라면, 두 개의 마을로 쪼개진 것으로 간주
    edge top;
    while(rootCount > 2) {
        // 현재 길의 유지비가 가장 작은 길
        top = edges.top();
        edges.pop();

        // 이어진 두 집과 현재 길의 유지비
        a = top.second.first;
        b = top.second.second;
        c = top.first;

        // 각 집의 최상위 노드 탐색
        getRoot(parent, a);
        getRoot(parent, b);

        // 최상위 노드가 같다면, 이미 집 사이에 경로가 있는 것으로 간주
        // (다른 간선을 통해 집과 집이 직간접적으로 이어져 있음)
        if(parent[a] == parent[b])
            continue;
        
        // 만약 두 집이 연결되어 있지 않다면, 최상위 노드 통일
        parent[getRoot(parent, a)] = getRoot(parent, b);
        // 최소 비용 합산
        cost += c;
        // 최상위 노드 개수 감소
        rootCount--;
    }

    // 길의 유지비의 최솟값 출력
    cout << cost << endl;
    return 0;
}