[BOJ] 백준 14950. 정복자 (Gold III)

마찬가지로 solvedac 빼빼로 이벤트때문에 막대과자 얻으려고 둘러보다가 발견한 문제.

근데 정말 문제를 잘만드신 것 같다.

문제는 아래와 같다.

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

14950번: 정복자

이 문제는 알고리즘 분류를 보지 말고 풀길 바란다.

오로지 알고리즘 분류를 떠올리는 난이도 때문에 티어가 올라간 문제라 생각된다.

---

의식의 흐름 및 해설

1번부터 시작해야되는데, 최소비용으로 접근해야 되니까 BFS를 생각해봤다. BFS는 간선 비용이 있기 때문에 안되고,

dijkstra는 반드시 도착지점이 바로 출발지점으로 돼야 했기 때문에 불가능해보였다.

 

그런데 어차피 모든 도시를 다 이으려면 1번에서 출발하든, 어디서 출발하든, 1번과 연결되는 다리는 최소 1개 이상 존재할 것이다.

그리고 비용은 어차피 1번에서 출발하든, 어디서 출발하든 무조건 최소 개수의 다리로 짓는 것이 제일 좋다. mst는 트리이므로 무조건 최소 개수의 다리로 짓기 때문에 상관없다.

따라서 그냥 mst로 다 연결해버리면 된다.

 

mst임이 쉽게 보이지 않았던 이유는, 1번부터 출발해야 된다는 점과 다리를 연결할수록 증가되는 비용 때문이 아닐까 싶다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 10011;
const double INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M, T, p[MAX];
vector<pii> v;
int find(int a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return false;
	if (a > b)swap(a, b);
	p[b] = a;
	return true;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		p[i] = i;
	}
	while (M--) {
		int a, b, cost;
		cin >> a >> b >> cost;
		v.push_back({ cost, {a,b} });
	}
	sort(all(v));
	ll ans = 0, cnt = 0;
	for (int i = 0; i < v.size(); i++) {
		int n1 = v[i].second.first;
		int n2 = v[i].second.second;
		int cost = v[i].first;
		if (find(n1) != find(n2)) {
			merge(n1, n2);
			ans += 1LL * cost;
			ans += cnt++ * T;
		}
	}
	cout << ans << "\n";
}

---

다른 알고리즘으로 삽질하기 쉽다고 생각되는 문제.