백준 20010 악덕 영주 혜유

문제링크

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

문제

풀이

1. 크루스칼 알고리즘을 통해 최소신장 트리 만들기
2. 최소신장 트리를 만들면서 최소 신장트리의 연결정보를 linked 배열에 저장
3. 최소신장트리 완성 후 마을 간 연결 정보 중에서 가장 큰 비용을 구하기 위해 dfs를 통해 linked 배열을 탐색
4. dfs 탐색시 각 단말노드를 시작점으로 잡고 탐색 시작

코드

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

int n, k;
int parents[1001];
vector<pair<int, pair<int, int>>> v;
vector<pair<int, int>> linked[1001];

void init() {
	for (int i = 0; i < 1001; i++) parents[i] = i;
}

int find_parents(int x) {
	if (parents[x] == x) return x;
	else return parents[x] = find_parents(parents[x]);
}

int union_parents(int a, int b) {
	int p1 = find_parents(a);
	int p2 = find_parents(b);
	if (p1 != p2) {
		parents[p1] = p2;
		return 1;
	}
	return 0;
}

int find_max2(int start, int before, int max_cost) {
	int ans = 0;
	for (int i = 0; i < linked[start].size(); i++) {
		if (linked[start][i].second == before) continue;
		ans = max(ans, find_max2(linked[start][i].second, start, max_cost + linked[start][i].first));
	}
	ans = max(ans, max_cost);
	return ans;
}

int find_max() {
	int max_cost = 0;
	for (int i = 0; i < n; i++) {
		if (linked[i].size() == 1) {
			max_cost = max(max_cost, find_max2(i, -1, 0));
		}
	}
	return max_cost;
}

int make_mst() {
	int mst_sum = 0;
	for (int i = 0; i < v.size(); i++) {
		int cost = v[i].first;
		int a = v[i].second.first;
		int b = v[i].second.second;
		if (union_parents(a, b)) {
			mst_sum += cost;
			linked[a].push_back({ cost,b });
			linked[b].push_back({ cost,a });
		}
	}
	return mst_sum;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	init();

	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		v.push_back({ cost,{a,b} });
	}
	sort(v.begin(), v.end());
	cout << make_mst() << '\n';
	cout << find_max();
}

후기

익숙한 알고리즘이라 어렵지는 않았는데 코드가 너무 지저분하다. 깔끔하게 짜는 연습도 하자.