취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1185번 문제인 유럽여행이다.
문제는 아래 링크를 확인하자.

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

길을 없앤 뒤의 그래프의 모습은 원래의 그래프의 스패닝 트리와 같음을 관찰하자. 또한, 이 스패닝 트리의 한 점에서 출발해 모든 노드를 적어도 한 번씩 찍고 출발노드로 돌아오는 가장 효율적인 경로는 DFS와 같은 탐색경로임을 관찰하자.

DFS의 과정을 생각하면 모든 에지는 정확히 한번씩 양방향으로 이동하고, 모든 노드는 해당 노드의 차수(degree)회 방문하게 됨(단, 출발노드는 +1)을 알 수 있다. 이 점에서 스패닝 트리가 주어지면 출발노드는 "가장 비용이 적은 노드"를 고르는 것이 항상 이득임을 관찰하자. 한편 모든 스패닝 트리는 같은 노드집합을 공유하므로, 출발 노드는 항상 "가장 비용이 적은 노드"가 됨을 알 수 있다.

이제 각 에지를 고른 것이 비용에 얼마나 영향을 주었는지를 생각해보자. 먼저, 이 에지를 두 번 지나므로 (에지의 비용)*2만큼의 비용이 추가된다. 또한, 해당 에지를 추가하는 것으로 이 에지가 연결하는 양 끝의 노드를 한번씩 더 지나게 되었으므로 (에지가 연결하는 양 끝 노드의 비용의 합)만큼의 비용 또한 추가된다. 이 외의 비용이 추가되지는 않는다.

위와 같이 스패닝 트리의 비용에 영향을 주는 값을 에지의 새로운 비용으로 하는 새 그래프를 모델링했을 때, 이 그래프의 MST의 비용과 원 그래프의 출발노드의 비용(즉, 노드 비용의 최솟값)을 더한 값이 문제의 답과 같음을 관찰하자.

해당 관찰을 이용하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int uf[10001];
int findf(int cur) {
	if (cur == uf[cur]) return cur;
	return uf[cur] = findf(uf[cur]);
}

int N, M;
int C[10001];
pair<int, pair<int, int>> edges[100000];

int ans = 1000000007;

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		int c; cin >> c;
		ans = min(ans, c);
		C[i] = c;
	}

	for (int m = 0; m < M; m++) {
		int s, e, l; cin >> s >> e >> l;
		edges[m] = make_pair(2 * l + C[s] + C[e], make_pair(s, e));
	}

	sort(edges, edges + M);
	for (int i = 1; i <= N; i++) uf[i] = i;

	for (int m = 0; m < M; m++) {
		auto& cur = edges[m];
		int w = cur.first, s = findf(cur.second.first), e = findf(cur.second.second);
		if (s == e) continue;
		ans += w, uf[e] = s;
	}

	cout << ans;
}