백준 1647번 [도시 분할 계획](C++) -yes6686- 티스토리

백준 문제 풀이: 1647 [도시 분할 계획]

---

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

문제 설명:

도시를 두 개의 구역으로 분리하려고 합니다. 도시에는 집과 길이 있으며, 모든 길은 유지 비용이 있습니다. 길을 최소한으로 선택하여 모든 집들이 연결되도록 하고, 두 구역으로 나누었을 때의 최소 비용을 구하는 문제입니다. 단, 두 구역 사이에 길이 없어야 합니다.

---

문제 해결 코드

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

int parent[100001];

// 부모 노드 찾기
int GetParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = GetParent(parent[x]);
}

// 두 노드를 합치기
void unionParent(int a, int b) {
    a = GetParent(a);
    b = GetParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}

// 같은 부모를 가지는지 확인
int findParent(int a, int b) {
    a = GetParent(a);
    b = GetParent(b);
    return a == b;
}

// 간선 구조체 정의
struct edge {
    int x, y, cost;
};

// 간선 비교 함수
bool compare(edge a, edge b) {
    return a.cost < b.cost;
}

edge Ed[1000001];

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

    int n, m;
    cin >> n >> m;

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

    for (int i = 0; i < m; i++) {
        cin >> Ed[i].x >> Ed[i].y >> Ed[i].cost;
    }

    // 간선 정렬
    sort(Ed, Ed + m, compare);

    int sum = 0, maxCost = -1;

    // 최소 신장 트리 구성
    for (int i = 0; i < m; i++) {
        if (!findParent(Ed[i].x, Ed[i].y)) {
            unionParent(Ed[i].x, Ed[i].y);
            sum += Ed[i].cost;
            maxCost = max(maxCost, Ed[i].cost);
        }
    }

    // 가장 비싼 간선 제거 후 출력
    cout << sum - maxCost;
}

예제

입력:
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

출력:
8

---

코드 설명

• 입력 및 초기화: 각 집과 길의 정보를 입력받고, 부모 노드 배열을 초기화합니다.
• 간선 정렬: 모든 길을 비용 기준으로 오름차순 정렬합니다.
• 최소 신장 트리 구성:
  • 사이클이 발생하지 않도록 간선을 선택합니다.
  • 선택한 간선의 비용을 합산하고, 최대 비용을 기록합니다.
• 결과 출력: 최소 신장 트리의 총 비용에서 가장 비싼 간선의 비용을 뺀 값을 출력합니다.

시간 복잡도

• 간선 정렬: O(M log M), M은 간선의 수
• 유니온-파인드: O(M α(N)), α는 아커만 함수의 역함수
• 전체 시간 복잡도: O(M log M)

---

결과

최소 신장 트리의 구성에서 두 구역으로 나눌 수 있는 최소 비용을 효율적으로 구할 수 있습니다.