[백준 1647번] 도시 분할 계획

푼 문제

1647번: 도시 분할 계획

문제 설명

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.
마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

풀기 전 한 생각

문제 설명에서 가장 중요한 포인트를 잡아보자면, "어느 방향으로든지 다닐 수 있는 편리한 길", "두 집 사이에 경로가 항상 존재", "임의의 두 집 사이에 경로가 항상 존재", "길의 유지비의 합을 최소로"이다. 무방향 가중치 그래프에서 모든 노드를 한번씩 방문하는 최소 신장 트리(MST) 문제이므로, 프림 또는 크루스칼로 풀 수 있다. 이때 "길이 너무 많다", 즉 간선이 많다고 했으므로, 간선의 개수가 많은 밀집 그래프(Dense Graph)에서 효율적인 프림 알고리즘을 쓰면 된다. 간단하게 계산해보면 프림의 경우 (우선순위 큐 구현 시) O(ElogV)이므로, worst case에서 1,000,000*log2(100,000) = 5,000,000이고, 크루스칼의 경우 O(ElogE)이므로, 1,000,000*log2(1,000,000) = 6,000,000이다. 프림을 쓰는 게 효율적이다.

실수한 점

이렇게 해서 우선순위 큐로 프림을 구현했는데, 답이 틀리게 나왔다. 그 이유는 마을 분할 자체도 내가 구현해야 하는 것이기 때문이다. 즉 마을 1과 마을 2에 각각 들어갈 노드를 내가 구하고, 각 마을 내에서의 간선 합이 최소가 되게 해야 한다. 이를 위해서는 1) 먼저 노드를 마을 1과 마을 2로 분할했을 때 트리가 만들어져야 하고, 2) 그렇게 만들어진 두 개의 트리에서 각각 MST를 구해야 한다.

마을 1과 마을 2를 나눌 때 노드를 선택하기 위해서 브루트 포스를 사용한다고 생각해보면 worst case에서 100,000C1 + 100,000C2 + ... 100,000C50,000가 되겠는데, 굳이 계산해보지 않아도 이 기준을 쓰면 안 될 것 같다.

이 문제는 트리의 특성을 생각해보면 간단하게 해결 가능하다. 트리에서 간선 하나를 제거하면 두 개의 트리가 만들어진다. 아래 그림을 보면 이해할 수 있다.

그림으로 보여준 트리가 너무 단순해서 이 방식이 통하는 게 아니라 모든 트리에서 통하는 방법이다. 나무(진짜 말 그대로 나무)에서 가지 하나를 꺾어도 원본 나무와 꺾인 가지 모두 각각은 잘 연결되어 있는 것을 생각해보면 이해가 될 것 같다. 이 점을 고려하면 정답으로 나온 MST에서 가장 높은 가중치를 가진 간선 하나만 제외해주면 마을 2개가 최소 비용으로 만들어진다는 것을 알 수 있다. 즉 노드를 분할하는 것을 먼저 생각하지 말고, 일단 MST를 구한 후 간선 하나를 제외해서 트리를 2개 만들어주면 된다.

올바른 풀이 코드

#include <climits>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> ci;

int solution(int n, int start, vector<vector<ci>> &graph) {
    int answer = 0;
    int max = -1;
    vector<bool> visited(n + 1, false); // 정점 방문 여부
    vector<int> distance(n + 1, INT_MAX);
    // 큐에 저장되는 요소(ci), 내부 구현에 쓰는 컨테이너(vector), 정렬(오름차순)
    priority_queue<ci, vector<ci>, greater<>> pq;

    // 초기화
    pq.push(make_pair(0, start));
    distance[start] = 0;

    // 큐가 비어있지 않으면 실행
    while (!pq.empty()) {
        auto [curr_w, curr] = pq.top();
        pq.pop();

        // 이미 방문했었다면 continue
        if (visited[curr]) {
            continue;
        }

        // 처음 방문이라면 방문 처리 및 가중치 더하기
        visited[curr] = true;
        answer += curr_w;

        // 마을을 두 개로 나누어 줄 때 제거할 가장 큰 길(가중치)
        if (max < curr_w) {
            max = curr_w;
        }

        for (auto [next_w, next] : graph[curr]) {
            if (!visited[next] && next_w < distance[next]) {
                // 미방문 정점이면서 & 현재 기록된 간선보다 작은 가중치가 나왔을 경우
                pq.push(make_pair(next_w, next));
                distance[next] = next_w;
            }
        }
    }
    return answer - max;
}

// 시간 복잡도: 프림의 경우 우선순위 큐 구현 시 O(ElogV)이므로, worst case에서 1,000,000*log2(100,000) = 5,000,000
// 크루스칼의 경우 O(ElogE)이므로, 1,000,000*log2(1,000,000) = 6,000,000
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m; // 집의 개수 N(2 ≤ N ≤ 100,000), 길의 개수 M(1 ≤ M ≤ 1,000,000)
    cin >> n >> m;
    vector<vector<ci>> graph(n + 1, vector<ci>(0)); // 각 노드의 연결 된 노드 linked list

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back(make_pair(w, b));
        graph[b].push_back(make_pair(w, a));
    }

    cout << solution(n, 1, graph); // 무방향이므로 아무 노드에서나 시작해도 됨
}

메모리는 35112 KB, 시간은 516 ms가 소요되었다.

배운 점

작은 트리를 만들어야 하는 문제는 먼저 전체 그래프에서 큰 트리를 만든 후, 간선을 제거해서 작은 트리로 만들어주면 된다는 점을 배우게 되었다.