[백준] 1647 도시 분할 계획

1647번: 도시 분할 계획

 

boj.kr

풀이

이 문제는 최소한의 비용으로 두 마을을 만들어야하는데, 결국 1개의 최소 스패닝 트리를 만들고 그 중에 가장 큰 간선을 제거해주면 최소한의 비용으로 2개의 마을을 만든 것과 같다. 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 만들어서 해결하였다.

코드

C++

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

int n, m;
vector<pair<int, pair<int, int>>> edges;
vector<int> root;

int find(int v) {
    if (root[v] != v)
        root[v] = find(root[v]);
    return root[v];
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);

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

int kruskal() {
    int last = 0;
    int sum = 0;

    for (int i = 0; i < edges.size(); i++) {
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        int c = edges[i].first;
        if (find(a) == find(b)) continue;
        merge(a, b);
        sum += c;
        last = c;
    }
    return sum - last;
}

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

    cin >> n >> m;
    root = vector<int>(n + 1);

    for (int i = 1; i <= n; i++)
        root[i] = i;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({ c, {a, b} });
    }
    sort(edges.begin(), edges.end());
    cout << kruskal() << '\n';
    return 0;
}

Python3

import sys


def find(x):
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]


def union(a, b):
    a = find(a)
    b = find(b)

    if a < b:
        root[b] = a
    else:
        root[a] = b


def kruskal():
    sum = 0
    last = 0
    for i in edges:
        c, a, b = i
        if find(a) == find(b):
            continue
        union(a, b)
        sum += c
        last = c
    return sum - last


n, m = map(int, sys.stdin.readline().rstrip().split())
root = [0 for _ in range(n + 1)]
edges = []

for i in range(1, n + 1):
    root[i] = i

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    edges.append((c, a, b))
edges.sort()

print(kruskal())