[BOJ] #1647 도시 분할 계획

https://www.acmicpc.net/problem/1647

---

최소 신장 트리, MST를 다루는 기본적인 문제이다.

인접리스트 형태로 주어지는 그래프에 대해 MST를 생성하면 되는 문제인데, 한가지 조건이 더 붙었다. 해당 MST를 두 집합으로 나누어서 가중치의 합이 가장 적은 MST 형태를 만들어 내면 되는 것이다. 당연히 그래프를 둘로 나누고 할 필요없이 결론적으로는 MST를 생성하여 구해진 가중치의 합에서 가장 가중치가 큰 간선을 빼주면 된다.

이렇게 방향성을 잡고 풀면 되는데 MST 구현에는 보통 두가지 접근 방식이 있다. 하나는 프림 알고리즘 (Prim's Algorithm) 이고, 다른 하나는 크루스칼 알고리즘 (Kruskal's Algorithm) 이다. 전자는 우선순위 큐와 방문여부를 체크하는 visited 배열을 사용하고, 후자는 정렬 알고리즘과 사이클을 방지하는 유니온-파인드 기법을 사용하게 된다.

해당 알고리즘들에 대한 설명은 이전에 블로그에 게시해두었으니 참고하길 바란다.

https://jhoon-study.tistory.com/50

[알고리즘 공부] 크루스칼 알고리즘 Kruskal's Algorithm

https://jhoon-study.tistory.com/51

[알고리즘 공부] 프림 알고리즘 Prim's Algorithm

 

필자는 이 문제를 프림과 크루스칼 두 가지를 모두 사용하는 방식으로 풀어봤는데, 나름 재밌었던 것 같다. 다양한 문제를 여러개 많이 풀어보는 것도 좋지만, 한가지 문제를 곱씹어 보면서 다른 풀이법으로 여러번 풀어보는 것도 실력 향상에 굉장히 도움이 많이 된다고 생각하기 때문에 MST 구현하는 문제는 두 가지 방식 모두 한번 풀어보면 좋을 것 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX 100001
#define INF 999999

using namespace std;

int V,E;
vector<pair<int,int>> Graph[MAX];
bool visited[MAX];

int prim() {
    priority_queue<pair<int,int>> pq;
    int total = 0;
    int maxCost = 0;

    pq.push(make_pair(0,1));    //1에서부터 출발. 시작점이므로 가중치는 0

    while (!pq.empty()) {
        while (!pq.empty() && visited[pq.top().second]) pq.pop();
        if (pq.empty()) break;

        int curr = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();

        visited[curr] = true;
        total += cost;
        //cout << cost << ' ';
        maxCost = max(cost, maxCost);

        for (int j=0; j<Graph[curr].size(); j++) {
            int next = Graph[curr][j].first;
            int newCost = Graph[curr][j].second;

            if (visited[next] == false)
                pq.push(make_pair(-newCost, next));
        }
    }

    return total - maxCost;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> V >> E;

    for (int i=0; i<E; i++) {
        int A,B,C;
        cin >> A >> B >> C;

        Graph[A].push_back(make_pair(B,C));
        Graph[B].push_back(make_pair(A,C));
    }

    cout << prim() << '\n';

    return 0;
}

프림 알고리즘을 활용한 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 100001

using namespace std;

int V,E;

vector<pair<int,int>> Graph[MAX];
vector<pair<int, pair<int,int>>> Edge;
vector<int> parent;

int getParent(int x) {
    if (parent[x] == x) return x;

    return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);

    if (a<b) parent[b] = a;
    else parent[a] = b;
}

bool find(int a, int b) {
    return getParent(a) == getParent(b);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> V >> E;

    for (int i=0; i<E; i++) {
        int A,B,C;
        cin >> A >> B >> C;

        Graph[A].push_back(make_pair(B,C));
        Graph[B].push_back(make_pair(A,C));
    }

    for (int u=1; u<=V; u++) {
        for (int j=0; j<Graph[u].size(); j++) {
            int v = Graph[u][j].first;
            int cost = Graph[u][j].second;

            if (u<v) {
                Edge.push_back(make_pair(cost, make_pair(u,v)));
            }
        }
    }

    sort(Edge.begin(), Edge.end());

    parent.resize(V+1);
    for (int i=1; i<=V; i++)
        parent[i] = i;

    int total=0, maxCost=0;
    vector<pair<int,int>> MST;
    for (int i=0; i<Edge.size(); i++) {
        int cost = Edge[i].first;
        int u = Edge[i].second.first;
        int v = Edge[i].second.second;

        if (!find(u,v)) {
            total += cost;

            maxCost = max(cost, maxCost);

            MST.push_back(make_pair(u,v));
            unionParent(u,v);
        }
    }

    cout << total - maxCost << '\n';

    return 0;
}

크루스칼 알고리즘을 활용한 풀이

 

예제로 주어진 인접리스트로 구성된 MST 모습

---

첫번째와 두번째 정답이 프림 알고리즘을 활용한 풀이, 마지막 정답이 크루스칼 알고리즘을 활용한 풀이에 해당한다.