백준 1185 - 유럽여행(C++)

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

1185번: 유럽여행

어려운 최소 스패닝 트리 문제였습니다.

먼저, 문제를 풀기 위해서는 일반적인 최소 스패닝 트리의 방식으로 그래프를 구성하면 답이 다르다는 것을 알아야합니다.
간선의 가중치를 기준으로 오름차순 정렬해서 만든 그래프는 다음과 같은데, 답보다 더 큰 값이 나오는 것을 알 수 있습니다.

따라서, 간선의 가중치로 정렬을 한다면 안된다는 것을 알 수 있습니다.

그렇다면, 예제에 맞는 그래프를 역추적해서 찾아본다면 이와 같습니다.

해당 그래프처럼 만들기 위해서는 간선의 가중치 or 나라의 비용에 따른 정렬으로는 만들 수 없음을 알 수 있습니다.

하지만,  문제에서 주어진 나라들의 이동 방법을 따라가본다면 힌트가 보입니다.

4번에서 출발했을 때, 이동을 그려본다면, 모든 간선을 “2번씩만” 움직인다는 것을 확인할 수 있습니다.
또한, 다른 정점에서 출발했을 때도 최솟값을 찾는다면 항상 간선을 “2번씩만” 움직인다는 것도 확인 가능합니다.

그렇다면, X -> Y로 움직일 때의 비용은 “가중치*2 + X의 비용 + Y의 비용”이 듦을 알 수 있습니다.

따라서, 간선의 비용을 해당 값처럼 바뀐 뒤, 최소 스패닝 트리를 구현한다면 답이 나오게 됩니다.

(가장 작은 비용을 가진 나라에서 출발을 해야하니, 해당 값까지 더해주면 됩니다.)


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

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

using namespace std;

int N, P, min_cost = 987654321;
int country[10001];
int parent[10001];
typedef struct info{
	int x;
	int y;
	int cost;
}info;
vector<info> connect;

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

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

void Union(int x, int y){
	if(x < y) parent[x] = y;
	else parent[y] = x;
}

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

void solve(){
	reset_parent();
	sort(connect.begin(), connect.end(), cmp);
	int cost = 0;
	for(int i = 0; i < connect.size(); i++){
		int x = Find(connect[i].x);
		int y = Find(connect[i].y);
		if(x != y){
			Union(x, y);
			cost += connect[i].cost;
		}
	}	
	cout << cost + min_cost;
}

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

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