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

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

 

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

int n, m;
int parent[100001];
vector<vector<int>> edge;

int find(int a) {
    if (parent[a] == a) {
        return a;
    } else {
        parent[a] = find(parent[a]);
        return parent[a];
    }
}

void unionf(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

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

    cin >> n >> m;
    edge = vector<vector<int>>(m, vector<int>(3));

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

    for (int i = 0; i < m; i++) {
        cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
    }

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

    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (find(edge[i][1]) != find(edge[i][2])) {
            unionf(edge[i][1], edge[i][2]);
            ans += edge[i][0];
            cnt++;
        }
        if (cnt == n - 2) break;
    }

    cout << ans << '\n';
}

어떻게 풀어야 하는지 감이 안 잡혀 태그를 까고 풀었다.. MST 문제였다! MST(최소 신장 트리)는 그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소인 트리를 말한다. MST는 모든 마을이 연결된 상태이므로, 두 마을로 분할하려면 MST에서 가중치가 가장 큰 간선 하나를 제거하면 된다. 이러한 아이디어를 얻은 후 처음 제출한 코드이다. (WA)

 

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

int n, m;
int parent[100001];
vector<vector<int>> edge;

int find(int a) {
    if (parent[a] == a) {
        return a;
    } else {
        parent[a] = find(parent[a]);
        return parent[a];
    }
}

void unionf(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

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

    cin >> n >> m;
    edge = vector<vector<int>>(m, vector<int>(3));

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

    for (int i = 0; i < m; i++) {
        cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
    }

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

    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (cnt == n - 2) break;
        if (find(edge[i][1]) != find(edge[i][2])) {
            unionf(edge[i][1], edge[i][2]);
            ans += edge[i][0];
            cnt++;
        }
    }

    cout << ans << '\n';
}

왜 틀렸나 했더니 집이 애초에 2개밖에 없으면 길이 하나도 필요하지 않다는 것을 생각하지 못해서 틀린 것이었다. 그래서 cnt가 n-2인지 확인하는 if문을 앞으로 빼서 해결하였다. (AC)