[백준][C++] 1647 도시 분할 계획

 

 

알고리즘 종류

    - MST

 

 

사고 과정

    - (잠깐의 읽기입니다)몇 달만에 풀어보는 문제였습니다. 두 그룹으로 나누기 위한 경우의 수를 순열조합으로 계산했습니다. 그런데 1억개가 넘어서 다른 방법을 찾아야 할 것 같았습니다. 하지만, 일단 해보기로 했습니다. 너무 오랜만이라서 vector를 사용하는 방법도 잊었습니다. 그렇게 잘 때가 다 되었습니다. 그래서 해설을 보기로 했습니다. 

 

    - 목표는 마을을 두 개로 나누고 집을 잇는 경로의 최소 비용을 구하는 것입니다. 가장 먼저 떠오르는 방법은 아마도 다음과 같을 것 입니다. 1. 마을을 2개로 나눈다. 2. 마을에서 MST 알고리즘을 한다. 그런데, 이렇게 생각해 보면 어떨까요? 모든 집을 연결하는 최소 스패닝 트리를 먼저 구합니다. 이후, A집과 B집을 잇는 경로 중에 최대 경로를 지우게 된다면, 두 마을이 만들어지고 두 마을 내의 경로의 합은 최소가 됩니다. 즉, 최소 스패닝 트리로 최소 경로를 구하고, 경로 내에서 최대 경로를 빼주면 됩니다.

 

 

구현(C++)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
 
using namespace std;
 
int n, m;
int total=0, maxEdge = -1;
 
int isVisited[MAX];
 
vector<pair<int, int> > edge[MAX];
 
// 우선 순위 큐를 지역변수로 선언합니다.
priority_queue<pair<int, int> > pq;
 
void prim(int here){
    
    isVisited[here] = 1;
    
    // 이웃 정점과 경로 비용을 저장합니다.
    // 이웃 정점은 방문하지 않은 정점이어야 합니다.
    for(int i=0; i<edge[here].size(); i++){
        int next = edge[here][i].first;
        int cost = edge[here][i].second;
        
        if(isVisited[next] == 0){
            // 우선 순위 큐를 사용합니다. -를 하면 작은 수를 top으로 올릴 수 있습니다.
            pq.push({-cost, next});
        }
    }
    
    // 최소 트리 그룹에 포함된 간선 중에서 최소 값을 가져옵니다.
    while(!pq.empty()){
        int next = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        
        // 최소 간선을 가져왔는데, 이웃한 정점을 이미 방문했는지 확인합니다.
        if(isVisited[next] == 0){
            total += cost;
            maxEdge = max(maxEdge, cost);
            prim(next);
            return;
        }
    }
}
 
int main(){
    
    cin >> n >> m;
    
    for(int i=1; i<=m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        edge[x].push_back({y,c});
        edge[y].push_back({x,c});
    }
    
    // 정점 1에서 시작합니다. 어디서 시작하던지 상관 없습니다.
    prim(1);
    
    cout << total - maxEdge << endl;
}

 

 

시행착오

    1. 왜  우선 순위 큐를 지역변수로 선언했을까? 궁금해서 prim()에 넣고 돌려보니, 이유를 알 수 있었습니다. 이것은 제가 prim 알고리즘 동작을 잊고 있었기 때문입니다. prim 알고리즘은 최소 스패닝 트리 그룹 내에 추가된 정점들 중에서 최소 간선을 선택하는 것입니다. 만약에 우선 순위 큐를 prim() 내부에서 사용하면, 한 정점에 국한된 간선을 선택할 수 있습니다. Dijkstra와 헷갈렸습니다.

 

    2. while(!pq.empty()){}를 할 필요가 있을까? 항상 우선 순위 큐 위에 있는 것을 가져오면 쉬울 것이라고 생각했습니다. 그러나, 항상 맨 위에 있는 간선(최소 비용 간선)에 연결된 다음 정점이 항상 방문하지 않았다라고 보장할 수 없습니다. 최소 간선이지만 연결된 정점은 이미 방문했을 수도 있습니다. 

 

    3.  몇 달만에 해결책을 생각할려고 하니 쉽지 않았습니다. 지속적으로 공부해야겠습니다.