[BOJ 15835] Explorace(c++)

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

---

문제 개요

체크포인트(N개)와 경로(M개)로 이루어진 그래프에서, 모든 체크포인트 간에 이동이 가능하도록 경로를 선택해야 합니다. 위원회를 배치할 경로를 최소화하면서도 전체 연결성을 보장해야 하므로, 최소 총 거리의 경로 집합을 구하는 문제입니다.

• (1 ≤ T ≤ 10)
• (1 ≤ N ≤ 20) : 체크포인트 수
• (1 ≤ M ≤ N*(N-1)) : 경로 수
• (1 ≤ d ≤ 500) : 각 경로의 거리

---

문제 풀이

모든 노드를 최소 비용으로 연결하는 전형적인 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다.

핵심 아이디어:

크루스칼(Kruskal) 알고리즘을 적용합니다.

1. 간선 정렬: 모든 경로를 거리(비용) 기준 오름차순 정렬
2. Union-Find: 사이클이 생기지 않는 간선만 선택하여 트리를 확장
3. N-1개의 간선이 선택되면 모든 노드가 연결되므로 종료

Union-Find 구조:

• getPar(x): 경로 압축(Path Compression)을 이용해 루트 노드를 반환
• unionPar(x, y): 두 집합을 합치고, 이미 같은 집합이면 false를 반환하여 사이클 감지

---

코드

 

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

class node {
public:
    int x, y, cost;
    bool operator < (const node& other) const {
        return cost < other.cost;
    }
};

int n, m, res;
vector<node> v;
int par[21];

void init() {
    cin >> n >> m;
    v.clear();
    res = 0;
    for (int i = 1; i <= n; i++) {
        par[i] = i;
    }
    for (int i = 0; i < m; i++) {
        int x, y, cost;
        cin >> x >> y >> cost;
        v.push_back({ x, y, cost });
    }
    sort(v.begin(), v.end());
}

int getPar(int x) {
    if (x == par[x]) return x;
    else return par[x] = getPar(par[x]);
}

bool unionPar(int x, int y) {
    x = getPar(x);
    y = getPar(y);
    if (x == y) return false;
    par[y] = x;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        init();
        for (auto cur : v) {
            if (unionPar(cur.x, cur.y)) {
                res += cur.cost;
            }
        }
        cout << "Case #" << tc << ": " << res << " meters\n";
    }
    return 0;
}