백준 BOJ 최소 스패닝 트리 (MST) 문제 풀이 모음 220813

최근 최소 스패닝 트리 (MST) 문제들을 풀이하고 있는데, 문제 풀이 방식이 다들 상당히 비슷해서 모든 문제들의 풀이를 적는 것은 비효율적으로 보인다. (크루스칼이나 프림 알고리즘으로 모두 풀린다)

그들 중 별도의 아이디어가 필요한 문제들만 몇 개 풀이를 적어보려고 한다.

 

 

백준 BOJ 22570번 : Save your cats

문제 난이도 : Gold IV

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

마녀가 울타리로 고양이를 가두었다고 하며, 각 폐쇄된 공간에는 고양이가 갇혀있다.

울타리를 부수는 비용은 울타리의 길이에 해당할 때, 최소 비용으로 고양이를 모두 구하는 비용을 구하는 문제이다.

 

울타리들을 그래프의 간선이라고 생각해보자.

사이클이 존재하지 않으면 모든 고양이가 구출될 수 있으므로, 결국 트리를 만드는 최소 비용을 묻는 문제가 된다.

이 때 남은 트리의 간선들의 비용의 합이 최대라면 우리는 최소 비용으로 고양이를 구출한 것이 된다.

따라서 최대 스패닝 트리의 비용을 구해서 초기 그래프 전체 간선들의 비용의 합에서 빼주면 된다.

이는 크루스칼 알고리즘에서 cmp 배열에서 간선 정렬만 오름차순에서 내림차순으로 바꾸어주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { double a, b, c; };

bool cmp(s x, s y) { return x.c > y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<pair<double, double>> u(N+1);

    for(int i=1; i<=N; i++) cin >> u[i].first >> u[i].second;

    vector<s> adj(M);
    double sum = 0;

    for(int i=0; i<M; i++) {
        int a, b; cin >> a >> b;

        adj[i].a = a;
        adj[i].b = b;
        adj[i].c = sqrt(pow(u[a].first - u[b].first, 2) + pow(u[a].second - u[b].second, 2));

        sum += adj[i].c;
    }

    sort(adj.begin(), adj.end(), cmp);

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    double ans = 0, cnt = 0;

    for(int i=0; i<M; i++) {
        double a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) break;
    }

    cout << fixed;
    cout.precision(3);

    ans = sum - ans;

    cout << ans << "\n";
}

 

 

백준 BOJ 2406번 : 안정적인 네트워크

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

회사에 N개의 컴퓨터가 서로 연결되어 있고, 1번 컴퓨터는 나머지 컴퓨터와 모두 직접 연결되어 있다고 할 때, 어떤 연결 또는 컴퓨터가 끊어져도 다른 연결을 통해 서로 연결되어 있을 수 있도록 하는 최소 추가 간선 설치 비용을 구하는 문제이다.

 

1번 컴퓨터는 모든 컴퓨터들과 직접 연결되어 있으므로, 2 ~ N번 컴퓨터가 최소 스패닝 트리를 구성한다면 어떤 간선이 끊어져도 나머지 간선들을 통해 이동할 수 있다.

즉, 2 ~ N번 노드에서 최소 스패닝 트리를 구성할 때의 비용을 구하면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<s> adj;

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int cnt = 0;

    while(M--) {
        int a, b; cin >> a >> b;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        cnt++;
    }

    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) {
            int x; cin >> x;

            if(i == 1 || i >= j) continue;

            adj.push_back({i, j, x});
        }

    sort(adj.begin(), adj.end(), cmp);

    int ans = 0;
    vector<pair<int, int>> w;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        w.push_back({a, b});

        if(cnt == N-2) break;
    }

    cout << ans << " " << w.size() << "\n";

    for(int i=0; i<w.size(); i++)
        cout << w[i].first << " " << w[i].second << "\n";
}

 

 

백준 BOJ 1833번 : 고속철도 설계하기

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 도시 사이에 이미 설치된 도로가 있고, 여기에 몇 개의 도로를 더 설치하여 모든 도시 사이의 이동이 가능하게 할 때, 이미 설치된 도로를 포함하여 필요한 총 비용과 설치할 도로의 양 끝 도시들을 구하는 문제이다.

 

일단 이미 설치된 도로들에 대해 총 비용에 더해주고, 분리 집합을 이용해 연결 관계를 처리해준다.

만약 이미 설치한 도로의 양 끝 도시가 연결되지 않은 도시일 경우 cnt++를 해준다.

아직 설치되지 않은 도로일 경우 벡터에 저장해주고, 정렬하여 비용이 낮은 것부터 대입해보며 확인한다.

연결되지 않은 도시일 경우 도로를 설치하고 cnt++ 해주며, cnt 값이 N-1이 될 경우 트리가 완성되었다는 것이므로 답을 출력해주면 된다.

설치한 도로들의 목록은 모두 벡터에 저장하여 출력해줄 수 있도록 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<s> adj;

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int ans = 0, cnt = 0;

    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) {
            int x; cin >> x;

            if(i >= j) continue;

            if(x < 0) {
                if(f(i) != f(j)) {
                    v[f(i)] = f(j);

                    cnt++;
                }

                ans += abs(x);
            }
            else if(x > 0) adj.push_back({i, j, x});
        }

    if(cnt >= N-1) {
        cout << ans << " " << 0 << "\n";
        return 0;
    }

    sort(adj.begin(), adj.end(), cmp);

    vector<pair<int, int>> w;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        w.push_back({a, b});

        if(cnt == N-1) break;
    }

    cout << ans << " " << w.size() << "\n";

    for(int i=0; i<w.size(); i++)
        cout << w[i].first << " " << w[i].second << "\n";
}

 

 

백준 BOJ 1774번 : 우주신과의 교감

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

노드 N개의 위치가 주어지고, 몇 개의 간선은 이미 연결되어 있다고 할 때, 새로운 간선을 연결할 때 필요한 비용이 두 노드 사이의 거리라면 모든 노드 사이가 연결되게 하기 위해 필요한 최소 비용을 구하는 문제이다.

 

먼저 가능한 간선을 모두 adj 벡터에 넣어주고, 이미 연결된 간선은 비용을 0으로 하여 넣어주면 된다.

그러면 알아서 정렬 이후에 크루스칼 알고리즘에 의해 비용이 0인 것부터 골라서 트리의 간선에 포함시킬지 확인해보게 되기 때문이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { double  a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<pair<double, double>> u(N+1);

    for(int i=1; i<=N; i++) cin >> u[i].first >> u[i].second;

    vector<s> adj;

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++)
            adj.push_back({i, j, sqrt(pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2))});

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    for(int i=0; i<M; i++) {
        int a, b; cin >> a >> b;

        adj.push_back({a, b, 0});
    }

    sort(adj.begin(), adj.end(), cmp);

    double ans = 0, cnt = 0;

    for(int i=0; i<adj.size(); i++) {
        double a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) break;
    }

    cout << fixed;
    cout.precision(2);

    cout << ans << "\n";
}

 

 

백준 BOJ 1414번 : 불우이웃돕기

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 노드에 대해 i행 j열의 값이 i번 노드에서 j번 노드를 연결하는 비용인 N x N 크기의 인접 행렬이 주어질 때, 모든 노드가 연결되도록 하면서 제거할 수 있는 간선들의 최대 비용을 구하는 문제이다.

 

인접 행렬을 이용하여 그래프를 연결해준 뒤 최소 스패닝 트리를 구하고, 전체 비용에서 최소 스패닝 트리의 비용을 뺀 값을 답으로 얻어주면 된다.

예외 케이스는 N = 1인 경우인데, 이 경우는 간선을 하나도 추가하지 않아도 이미 트리인 상태이므로 따로 체크를 해주어야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<s> adj;
    int sum = 0;

    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) {
            char c; cin >> c;

            int x;

            if(c == '0') continue;
            else if(c >= 'a' && c <= 'z') x = c - 'a' + 1;
            else if(c >= 'A' && c <= 'Z') x = c - 'A' + 27;

            adj.push_back({i, j, x});
            sum += x;
        }

    sort(adj.begin(), adj.end(), cmp);

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int ans = 0, cnt = 0;
    bool check = false;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) {
            check = true;
            break;
        }
    }

    if(N > 1 && !check) {
        cout << -1 << "\n";
        return 0;
    }

    ans = sum - ans;

    cout << ans << "\n";
}

 

 

백준 BOJ 4722번 : Underground Cables

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

2차원 좌표 평면 상의 N개의 지점을 연결하는 케이블을 설치할 때, 두 케이블이 교차하지 않도록 하면서 모든 지점을 연결하는 케이블 길이 합의 최솟값을 구하는 문제이다.

 

N개의 지점을 최소 스패닝 트리로 연결할 경우 교차점이 발생하지 않는다.

귀류법으로 생각해보면 쉽게 이해할 수 있다. (만약 교차점이 발생하는 그래프가 최소 스패닝 트리라고 가정할 경우, 이 교차 지점을 풀어서 더 짧은 연결을 만들 수 있으므로 가정에 모순이 된다.)

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { double a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        vector<pair<double, double>> u(N+1);

        for(int i=1; i<=N; i++)
            cin >> u[i].first >> u[i].second;

        vector<s> adj;

        for(int i=1; i<=N; i++)
            for(int j=i+1; j<=N; j++)
                adj.push_back({i, j, sqrt(pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2))});

        sort(adj.begin(), adj.end(), cmp);

        v.clear();
        v.resize(N+1);
        for(int i=1; i<=N; i++) v[i] = i;

        double ans = 0, cnt = 0;

        for(int i=0; i<adj.size(); i++) {
            double a = adj[i].a, b = adj[i].b, c = adj[i].c;

            if(f(a) == f(b)) continue;

            v[f(a)] = f(b);

            ans += c;
            cnt++;

            if(cnt == N-1) break;
        }

        cout << fixed;
        cout.precision(2);

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 7439번 : Highways

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 도시와 2차원 평면 상의 좌표가 주어지고, M개의 이미 연결된 도로가 주어질 때, 새로운 도로를 건설하는데 드는 비용은 두 도시 사이의 거리에 비례한다고 한다면 최소 비용으로 모든 도시를 연결하기 위해 건설해야 하는 도로들의 목록을 구하는 문제이다.

 

분리 집합을 사용해 M개의 도로에 의해 이미 연결된 요소들의 개수를 포함하여, N-1개의 새로운 연결이 구성될 때까지 가까운 도로부터 검사해보면서 벡터에 추가하면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { double a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<pair<double, double>> u(N+1);

    for(int i=1; i<=N; i++)
        cin >> u[i].first >> u[i].second;

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int cnt = 0;

    int M; cin >> M;

    for(int i=0; i<M; i++) {
        int a, b; cin >> a >> b;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        cnt++;
    }

    if(cnt >= N-1) return 0;

    vector<s> adj;

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++)
            adj.push_back({i, j, sqrt(pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2))});

    sort(adj.begin(), adj.end(), cmp);

    vector<pair<int, int>> w;

    for(int i=0; i<adj.size(); i++) {
        double a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        cnt++;

        w.push_back({a, b});

        if(cnt == N-1) break;
    }

    for(int i=0; i<w.size(); i++)
        cout << w[i].first << " " << w[i].second << "\n";
}

 

 

백준 BOJ 10021번 : Watering the Fields

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 2차원 평면 상의 지점이 있고, 두 지점을 연결하는 비용이 거리의 제곱일 때, 비용이 M 이상인 거리만 연결이 가능하다면 모든 지점을 연결하는 데에 필요한 최소 비용을 구하는 문제이다.

 

adj 벡터에 값을 추가할 때 거리 제곱이 M 미만인 것은 추가하지 않으면 된다.

그러면 자연히 크루스칼 알고리즘이 작동할 때 cost가 M 이상인 간선에 대해서만 검사 및 추가가 발생하므로 문제에서 요구하는 답을 구할 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<pair<double, double>> u(N+1);

    for(int i=1; i<=N; i++)
        cin >> u[i].first >> u[i].second;

    vector<s> adj;

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++) {
            int cost = (u[i].first - u[j].first) * (u[i].first - u[j].first)
                        + (u[i].second - u[j].second) * (u[i].second - u[j].second);

            if(cost >= M) adj.push_back({i, j, cost});
        }

    sort(adj.begin(), adj.end(), cmp);

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int ans = 0, cnt = 0;
    bool check = false;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) {
            check = true;
            break;
        }
    }

    if(check) cout << ans << "\n";
    else cout << -1 << "\n";
}

 

 

백준 BOJ 13418번 : 학교 탐방하기

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

0번 노드에서 출발하여 N번까지 모든 노드에 도달하려고 하고 각 간선은 오르막길 또는 내리막길일 때, 피로도가 간선들 중 오르막길의 수의 제곱이라면, 피로도의 최댓값과 최솟값의 차이를 구하는 문제이다.

 

오르막길의 비용을 1로, 내리막길의 비용을 0으로 설정한 후 크루스칼 알고리즘을 서로 다른 두 번에 정렬에 대해 두 번 수행해준 뒤 얻어지는 비용의 제곱의 차를 답으로 얻어주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

bool cmp2(s x, s y) { return x.c > y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    M++;

    vector<s> adj(M);

    for(int i=0; i<M; i++) {
        cin >> adj[i].a >> adj[i].b >> adj[i].c;

        adj[i].c = 1 - adj[i].c;
    }

    sort(adj.begin(), adj.end(), cmp);

    v.clear();
    v.resize(N+1);
    for(int i=0; i<=N; i++) v[i] = i;

    int x = 0, cnt = 0;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        x += c;
        cnt++;

        if(cnt == N) break;
    }

    v.clear();
    v.resize(N+1);
    for(int i=0; i<=N; i++) v[i] = i;

    sort(adj.begin(), adj.end(), cmp2);

    int y = 0;
    cnt = 0;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        y += c;
        cnt++;

        if(cnt == N) break;
    }

    cout << abs(x*x - y*y) << "\n";
}

 

 

백준 BOJ 14167번 : Moocast

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 노드의 좌표가 주어지고, 비용 X를 지불하면 거리의 제곱이 X 이하인 모든 두 노드 사이의 연결이 가능하다고 할 때, 모든 노드 사이의 연결이 가능하려면 지불해야 하는 최소 비용을 구하는 문제이다.

 

최소 스패닝 트리를 구하고, 마지막으로 추가한 간선의 비용을 답으로 얻어주면 된다.

상당히 정석적인 MST 문제이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<pair<int, int>> u(N+1);

    for(int i=1; i<=N; i++) cin >> u[i].first >> u[i].second;

    vector<s> adj;

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++)
            adj.push_back({i, j, pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2)});

    sort(adj.begin(), adj.end(), cmp);

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int cnt = 0;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        cnt++;

        if(cnt == N-1) {
            cout << c << "\n";

            break;
        }
    }
}

 

 

백준 BOj 14401번 : 악덕 나라

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST), 기하학

 

N개의 도시의 좌표가 주어지고 이미 연결된 도로의 도시들이 주어질 때, 거리의 제곱이 도로 연결 비용이라면 추가로 설치할 도로의 개수를 최소로 하면서 그 때 비용이 최대가 하여 모든 도시들을 연결하는 비용을 구하는 문제이다.

 

먼저 최소 스패닝 트리 코드에서 compare 함수만 반대로 해주어 최대 스패닝 트리의 비용을 구해주도록 하면 거의 해결이 된다.

남은 해결해야 하는 부분은 세 도시가 하나의 직선에 위치하는 경우인데, 이 경우는 양 끝 점의 도시를 연결하는 도로는 가운데에 다른 도시가 있기 때문에 설치하지 않는 것으로 가정하고 있다. (예제 1을 참고해보면 그렇다.)

그렇기 때문에 크루스칼 알고리즘에서 만약 두 도시를 연결하는 직선 사이에 다른 도시가 위치한다면 해당 간선은 skip 해주어야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c > y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<pair<int, int>> u(N+1);

    for(int i=1; i<=N; i++) cin >> u[i].first >> u[i].second;

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int cnt = 0;

    while(M--) {
        int a, b; cin >> a >> b;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        cnt++;
    }

    if(cnt >= N-1) {
        cout << 0 << "\n";
        return 0;
    }

    vector<s> adj;

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++)
            adj.push_back({i, j, pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2)});

    sort(adj.begin(), adj.end(), cmp);

    int ans = 0;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        bool check = true;

        for(int j=1; j<=N; j++) {
            if(j == a || j == b) continue;

            if((u[j].second - u[a].second) * (u[b].first - u[a].first)
               == (u[b].second - u[a].second) * (u[j].first - u[a].first)
               && ((u[a].first < u[j].first && u[j].first < u[b].first)
                   || (u[b].first < u[j].first && u[j].first < u[a].first))) check = false;
        }

        if(!check) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) break;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 14621번 : 나만 안되는 연애

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 대학교가 있고 남초 대학교와 여초 대학교로 나뉠 때, M개의 연결되는 간선이 존재할 때 이들 중 일부 간선을 선택하여 남초 대학교와 여초 대학교만 직접적인 간선으로 연결되며, 간접적으로는 모든 대학교가 연결되게 하는 최소 간선 비용의 합을 구하는 문제이다.

 

같은 성별의 대학교는 어차피 조건에 의해 연결이 불가능하므로, adj 벡터에 두 대학교의 성별이 다른 경우만 추가해준 뒤 MST를 구해주면 된다.

MST가 존재하지 않는 경우는 모두 -1을 출력해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<char> u(N+1);
    for(int i=1; i<=N; i++) cin >> u[i];

    vector<s> adj;

    while(M--) {
        int a, b, c; cin >> a >> b >> c;

        if(u[a] != u[b]) adj.push_back({a, b, c});
    }

    sort(adj.begin(), adj.end(), cmp);

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int ans = 0, cnt = 0;
    bool check = false;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) {
            check = true;

            break;
        }
    }

    if(check) cout << ans << "\n";
    else cout << -1 << "\n";
}

 

 

백준 BOJ 14950번 : 정복자

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 도시가 있고 M개의 간선이 주어지며, 어떤 도시를 정복하기 위해서는 정복한 도시들과 도로가 연결되면 된다고 할 때 하나의 도시를 점령할 때마다 아직 점령하지 않은 간선의 비용이 K씩 증가한다면 1번 도시에서 시작하여 모든 도시를 점령하는데 필요한 최소 비용을 구하는 문제이다.

 

문제에서는 1번 도시에서 점령을 시작한다고 하였으나 어차피 모든 도시를 점령해야 하므로 점령 순서는 중요하지 않다.

따라서 최소 스패닝 트리를 구하면서, 간선 하나를 선택할 때마다 add 값에 K씩 더해서 간선을 선택할 때마다 add 값을 더해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M, K; cin >> N >> M >> K;

    vector<s> adj(M);

    for(int i=0; i<M; i++)
        cin >> adj[i].a >> adj[i].b >> adj[i].c;

    sort(adj.begin(), adj.end(), cmp);

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int ans = 0, cnt = 0, add = 0;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c + add;
        add += K;
        cnt++;

        if(cnt == N-1) break;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 16302번 : Jurassic Jigsaw

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

N개의 염기서열이 주어지고, 두 염기서열의 거리는 두 염기서열에서 염기가 다른 자리의 수라고 할 때, N개의 염기서열로 그래프를 구성하여 간선의 비용을 염기서열의 거리라고 하여 트리를 구성한다면 최소 비용이 얼마인지 구하는 문제이다.

 

N C 2개의 조합에 대해 거리를 구하고 adj 벡터에 넣은 뒤 크루스칼 알고리즘으로 MST를 구해주면 된다.

문자열 처리 부분만 조금 다르지 나머지는 일반 MST 문제와 다르지 않다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<string> u(N);
    for(int i=0; i<N; i++) cin >> u[i];

    vector<s> adj;

    for(int i=0; i<N; i++)
        for(int j=i+1; j<N; j++) {
            int cnt = 0;

            for(int k=0; k<M; k++)
                if(u[i][k] != u[j][k]) cnt++;

            adj.push_back({i, j, cnt});
        }

    sort(adj.begin(), adj.end(), cmp);

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int ans = 0, cnt = 0;
    vector<pair<int, int>> w;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        w.push_back({a, b});

        if(cnt == N-1) break;
    }

    cout << ans << "\n";

    for(int i=0; i<w.size(); i++)
        cout << w[i].first << " " << w[i].second << "\n";
}

 

 

백준 BOJ 16045번 : Treehouses

문제 난이도 : Gold III

알고리즘 분류 : 최소 스패닝 트리 (MST)

 

 

N개의 집이 있고, 이들 중 1 ~ M번은 이미 연결되어 있으며 K개의 간선이 주어질 때 간선의 길이가 비용에 해당할 때 최소 비용만으로 모든 집을 연결하는 비용을 구하는 문제이다.

 

분리 집합을 적절히 활용하여 1 ~ M번 집을 연결해주고, K개의 간선에 대해서도 연결해준다. (분리 집합이므로 이미 연결된 두 노드 사이는 추가로 연결하지 않는다.)

이제 N C 2개의 두 노드의 조합에 대해 거리를 구하여 adj 벡터에 넣어주고, 크루스칼 알고리즘을 사용하여 모두 연결이 될 때까지 간선을 추가해주면서 답을 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { double a, b, c; };

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cout << fixed;
    cout.precision(3);

    int N, M, K; cin >> N >> M >> K;

    vector<pair<double, double>> u(N+1);

    for(int i=1; i<=N; i++)
        cin >> u[i].first >> u[i].second;

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int cnt = 0;

    for(int i=1; i<=M; i++) {
        if(f(i) == f(1)) continue;

        v[f(i)] = f(1);

        cnt++;
    }

    while(K--) {
        int a, b; cin >> a >> b;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        cnt++;
    }

    if(cnt >= N-1) {
        cout << 0 << "\n";

        return 0;
    }

    vector<s> adj;

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++)
            adj.push_back({i, j, sqrt(pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2))});

    sort(adj.begin(), adj.end(), cmp);

    double ans = 0;

    for(int i=0; i<adj.size(); i++) {
        double a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) break;
    }

    cout << ans << "\n";
}