백준 1647

ALGORITHM
2025-09-03

도시 분할 계획

관련 개념

#최소 신장 트리 #그래프

문제

📌 1 단계 : 문제 분석하기

  • 처음에 보면 어려워 보이지만, 잘 생각해보면 쉽다
  • 모든 집이 연결되어 있으면서 그 합이 최소라는 말에서 힌트를 얻을 수 있다.
  • MST를 만든 후, 가중치가 가장 큰 길만 없애면 된다.

📌 2 단계 : 손으로 풀어보기

  • MST

📌 3 단계 : 슈도 코드 작성하기

  • 생략

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <tuple>
#include <algorithm>
 
using namespace std;
typedef tuple<int, int, int> triple;
 
class DisjointSet {
private:
    vector<int> parent;
    vector<int> size;
public:
    DisjointSet(int N) {
        parent.resize(N + 1);
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }
        size.resize(N + 1, 0);
    }
 
    int find(int i) {
        if (parent[i] == i) return i;
        else return parent[i] = find(parent[i]);
    }
 
    void unite(int i, int j) {
 
        int root_i = find(i);
        int root_j = find(j);
 
        parent[root_i] = root_j;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N, M;
 
    cin >> N >> M;
 
    DisjointSet union_find = DisjointSet(N);
 
    vector<triple> graph;
 
    vector<triple> answer;
 
    int ans = 0;
 
    for (int i = 0; i < M; i++) {
        int start, dest, weight;
        cin >> start >> dest >> weight;
        graph.push_back({ start, dest, weight });
    }
 
    // MST 시작
    sort(graph.begin(), graph.end(), [](const auto& a, const auto& b) {
        return get<2>(a) < get<2>(b);
    });
 
    for (auto& edge : graph) {
        // 사이클이 없다면
        if (union_find.find(get<0>(edge)) != union_find.find(get<1>(edge))) {
            answer.push_back(edge);
            union_find.unite(get<0>(edge), get<1>(edge));
        }
    }
 
    for (int i = 0; i < N - 2; i++) {
        ans += get<2>(answer[i]);
    }
 
    cout << ans;
    
}

📌 5 단계 : 배운점

  • 크루스칼의 방법을 활용했다.
  • 유니온 파인드랑 튜플의 방법을 잘 익혀두자