문제 푼 날짜 : 2021-09-27

문제

문제 링크 : https://www.acmicpc.net/problem/1647

접근 및 풀이

전체적으로 최소 스패닝 트리(MST)를 만드는 문제였다.
MST를 만드는 대표적인 알고리즘 중 크루스칼 알고리즘을 적용하여 풀었다.

그런데 문제의 조건에서 두 개의 마을로 나누고, 각 마을에 최소 집이 하나씩 존재해야 한다고 했기 때문에 전체적으로 MST를 구성해준 다음 가장 큰 간선을 가지는 노드를 잘라내주었다.

코드

// 백준 1647번 : 도시 분할 계획
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(vector<int> v1, vector<int> v2) {
    return v1[2] < v2[2];
}

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

void Union(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);

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

bool Find(int parent[], int a, int b) {
    return getParent(parent, a) == getParent(parent, b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M, ans = 0;
    int parent[100001];
    vector<pair<int, pair<int, int>>> road;
    vector<int> ret;

    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        road.push_back(make_pair(c, make_pair(a, b)));
    }
    sort(road.begin(), road.end());

    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
    for (auto r : road) {
        int from = r.second.first;
        int to = r.second.second;
        int cost = r.first;
        if (!Find(parent, from, to)) {
            Union(parent, from, to);
            ret.push_back(cost);
        }
    }
    for (int i = 0; i < ret.size() - 1; i++) {
        ans += ret[i];
    }
    cout << ans;
    return 0;
}

결과

피드백

왠지 모르게 시간초과가 계속나서 여기저기 고쳐보다가 입력을 받아오는 부분을 수정해주었다.
처음 구현했을 때, 입력을 받아오는 부분을 이 문제 풀이에서 받아온 것과 동일하게 구현했었는데,,, 정확히 왜 그런지 좀 더 공부해봐야될 것 같다.