[C++ 백준 풀이] 1197번 : 최소 스패닝 트리 / 1647번 : 도시 분할 계획 (크루스칼 알고리즘)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 '1197번 : 최소 스패닝 트리'와 '1647번 : 도시 분할 계획' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 다룰 개념은 '크루스칼 알고리즘'입니다.

 

 

1197번 : 최소 스패닝 트리

 

두 정점 사이의 간선의 가중치가 입력되어 그래프의 정보가 주어질 때, 최소 스패닝 트리의 가중치를 출력하는 문제입니다.

최소 스패닝 트리란, 모든 정점 사이의 한 개 이상의 경로가 존재하는 가장 적은 가중치를 가지는 트리를 말합니다.

V개의 노드가 있을 때 최소 스패닝 트리는 V-1개의 간선을 가지게 됩니다. (왜냐하면 V개 이상의 간선을 가질 경우 그들 중 하나를 제거하더라도 여전히 간선을 통해 모든 정점 사이의 경로가 존재하기 때문입니다.)

따라서 어떻게 하면 가장 작은 합을 가지는 V-1개의 간선을 선택할 수 있을지 고민해보면 됩니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int parent[10001], sum = 0;
vector<pair<pair<int, int>, int>> line;
bool compare(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) { return a.second < b.second; }

int find_parent(int node) {
    if(parent[node] == node) return node;
    else return parent[node] = find_parent(parent[node]);
}

int main() {
    int V, E, A, B, C;
    scanf("%d %d", &V, &E);
    for(int i=0; i<E; i++) {
        scanf("%d %d %d", &A, &B, &C);
        line.push_back({{A, B}, C});
    }
    sort(line.begin(), line.end(), compare);
    for(int i=1; i<=V; i++) parent[i] = i;
    for(int i=0; i<E; i++) {
        if(find_parent(line[i].first.first) != find_parent(line[i].first.second)) {
            parent[find_parent(line[i].first.first)] = find_parent(line[i].first.second);
            sum += line[i].second;
        }
    }
    printf("%d", sum);
}

 

이 문제를 풀기 위해서는 크루스칼 알고리즘이나 프림 알고리즘을 알고 있으면 좋습니다.

여기서는 크루스칼 알고리즘을 사용할 것인데, 알고리즘의 과정은 다음과 같습니다.

 

1. 먼저 모든 간선들의 가중치를 오름차순으로 정렬합니다.

2. 가장 작은 간선부터 검사하면서, 이 간선의 양 끝점 사이의 기존의 경로가 있는지 확인하여 없으면 간선을 추가하고 경로가 있으면 간선을 추가하지 않고 건너뜁니다.

3. V-1개의 간선을 추가하였으면 검사를 종료해도 되지만, 그렇지 않아도 문제를 해결할 수는 있습니다. (이 문제의 풀이 코드에서는 해당 조건 없이 모든 간선을 검사하였습니다.)

 

위의 코드에서 핵심 부분은 find_parent 함수라고 생각하는데, DFS와 비슷한 탐색 방식으로 어떤 노드의 최상위 parent를 재귀적으로 찾기 때문입니다.

이러한 재귀적 구현이 없으면 풀이를 작성하기 아주 어려울 것입니다.

 

어쨌든 sort 함수로 간선 가중치 정렬 → 각 노드의 parent를 자기 자신으로 설정 → 검사를 통해 동일한 최상위 parent를 가졌는지 확인하고, 그렇지 않다면 연결을 해나가면서 parent를 갱신하는 과정을 통해 문제를 해결함을 확인할 수 있습니다.

 

 

위 코드의 12행을 parent[node] = find_parent(parent[node])로 받아서 return 하지 않고 바로 return find_parent(parent[node])로 작성할 경우 아래의 경우처럼 거의 10배의 시간이 소모되게 됩니다.

따라서 재귀적으로 parent를 찾되 = 연산자로 값을 왼쪽으로 받아서 넘겨야 합니다.

 

 

1647번 : 도시 분할 계획

 

1647번 문제인 도시 분할 계획 역시 동일한 알고리즘으로 해결이 가능한 문제입니다.

문제를 보면 분리된 두 마을 각각은 마을 내의 어떤 두 집이든 연결이 되어야 한다고 하였는데, 이것은 중의적 표현이 될 수 있으나 여러 간선을 통해서 연결이 되어도 된다는 뜻입니다. (complete graph가 아니라, 건너건너 연결만 되면 된다는 뜻)

이 문제는 잘 생각해보면 최소 스패닝 트리를 구하고 거기서 가장 가중치가 큰 간선 하나를 빼면 두 개의 스패닝 트리가 만들어짐을 알 수 있습니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int parent[100001], sum = 0, last;
vector<pair<pair<int, int>, int>> line;
bool compare(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) { return a.second < b.second; }

int find_parent(int node) {
    if(parent[node] == node) return node;
    else return parent[node] = find_parent(parent[node]);
}

int main() {
    int V, E, A, B, C;
    scanf("%d %d", &V, &E);
    for(int i=0; i<E; i++) {
        scanf("%d %d %d", &A, &B, &C);
        line.push_back({{A, B}, C});
    }
    sort(line.begin(), line.end(), compare);
    for(int i=1; i<=V; i++) parent[i] = i;
    for(int i=0; i<E; i++) {
        if(find_parent(line[i].first.first) != find_parent(line[i].first.second)) {
            parent[find_parent(line[i].first.first)] = find_parent(line[i].first.second);
            sum += line[i].second;
            last = line[i].second;
        }
    }
    printf("%d", sum-last);
}

 

풀이 코드를 보면 알겠지만 위의 문제와 거의 동일하게 해결이 됩니다.

간선들의 경우 가중치의 오름차순으로 정렬했기 때문에 마지막에 추가한 간선만 빼주면 됩니다.

따라서 last 변수에 마지막에 추가한 가중치를 계속 저장하다가, 탐색이 완료되면 빼주는 방식을 사용했습니다.

 

 

풀이 코드를 제출해보면, 516ms라는 짧지 않은 시간에 해결이 됨을 알 수 있습니다.

제 생각에는 앞서 말했듯 3번 조건과 같이 V-2개의 간선을 추가했을 때 즉시 종료하는 코드를 통해 더 빨리 해결할 수 있을 것 같습니다.

 

 

+ 실제로 고쳐서 제출해 보았는데 거의 변화는 없네요. (if cnt == V-2이면 break 하도록 작성)

   더 빨리 해결하기 위해서는 다른 알고리즘을 사용해야 할 것 같습니다.