백준 20010 - 악덕 영주 헤유(C++)

문제 링크입니다. https://www.acmicpc.net/problem/20010

20010번: 악덕 영주 혜유

다익스트라와 DFS를 이용한 문제입니다.

주어진 교역로를 통해 마을들끼리 서로 연결될 수 있는 최소 비용을 구하고, 해당 연결에서 가장 큰 경로의 비용을 구하는 문제입니다.

최소 비용으로 모든 마을이 연결될 수 있게 만드는 것은 최소 스패닝 트리를 통해 쉽게 구할 수 있습니다.

문제는 가장 큰 경로의 비용을 구하는 것인데, 간단하게 최소 스패닝 트리를 구하는 과정에서 가장 작은 비용의 간선을 구한 뒤,
연결하는 최소 비용에서 해당 값을 빼면 된다고 생각할 수 있습니다.

하지만 이것는 명백하게 잘못된 방법입니다.
왜나하면, 가장 작은 비용의 간선이 MST의 중간에 위치한다면 다른 정점들을 못가게 되는데,
정작 구하는 값은 해당 정점들을 간 것으로 치기 때문입니다.

따라서, 다른 방법을 이용해야 합니다.
만약, MST를 구하는 과정에서 서로 연결되는 정점들이 있는 경우에 이들의 값을 저장한다면
값을 통해 그래프 탐색을 할 수 있게 됩니다.
여기서, 최대 비용을 구하는 문제이니 BFS가 아닌 DFS를 이용해 모든 경우를 확인하는 방법을 사용하면 됩니다.

정리하자면 MST를 통해 최소 비용을 구한다. -> MST를 통해 저장된 간선들을 통해 DFS를 실행해 최대 비용을 구한다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;

int N, M;
int max_pay, min_cost;
typedef struct info{
	int x;
	int y;
	int cost;
}info;
vector<info> connect;
vector<pair<int, int>> line[1001];
int parent[1001];
int check[1001];


void reset_parent(){
	for(int i = 0; i < N; i++){
		parent[i] = i;
	}
}

bool cmp(info a, info b){
	if(a.cost < b.cost) return true;
	else return false;
}

int Find(int x){
	if(x == parent[x]) return x;
	else return parent[x] = Find(parent[x]);
}

void MST(){
	min_cost = 0;
	reset_parent();
	for(int i = 0; i < connect.size(); i++){
		int x = Find(connect[i].x);
		int y = Find(connect[i].y);
		if(x != y){
			parent[x] = y;
			min_cost += connect[i].cost;
			line[connect[i].x].push_back({connect[i].y, connect[i].cost});
			line[connect[i].y].push_back({connect[i].x, connect[i].cost});
		}
	}
}

void find_worst(int x, int cost){
	check[x] = 1;
	max_pay = max(max_pay, cost);
	for(int i = 0; i < line[x].size(); i++){
		int xx = line[x][i].first;
		int n_cost = cost + line[x][i].second;
		if(check[xx] == 0) find_worst(xx, n_cost);
	}
}

void solve(){
	sort(connect.begin(), connect.end(), cmp);
	MST();
	cout << min_cost << "\n";
	for(int i = 0; i < N; i++){
		memset(check, 0, sizeof(check));
		find_worst(i, 0);
	}
	cout << max_pay;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		connect.push_back({x, y, cost});
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.