백준 10423: 전기가 부족해

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

 

다익스트라?

이 문제를 보았을 때 먼저 떠올린 해결책이다.

발전소 위치 마다 다익스트라를 돌린 뒤에, 각 도시 위치를 순회하며 가장 적은 거리를 가진 발전소 위치를 정답에 더하면 어떨까? 란 생각을 했었다.

 

다익스트라의 시간복잡도를 검색하니, O(E log V)다. 즉, 이 문제의 그래프에서 다익스트라 한번은,

100,000 * log(1000) => 약 100만이고, 이것을 각 노드에서 한번씩 실행하면, 약 10억의 시간복잡도를 지닌다.

보통 한 문제의 시간복잡도는 많아도 1000만이 적절하다. 따라서, 이 아이디어는 절대로 아니다.

 

최소 스패닝 트리?

다른 아이디어로 최소 스패닝 트리를 사용하면 어떨까? 란 생각을 해보았다.

사실 이 문제를 보았을 때, 어째서인지, 최소 스패닝 트리가 먼저 떠올랐는데, 어떻게 사용할지 감이 안 잡혀서, 다익스트라 측면에서 먼저 생각했었다. 결국엔 다시 처음으로 돌아왔지만.

 

지금까지, 나는 최소 스패닝 트리를 풀 때, 크루스칼 알고리즘만을 사용했는데, 혹시 이 문제를 해결할때는 프림 알고리즘을 사용해 보는 것이 어떨까란 생각을 했다. 프림 알고리즘은, 시작 정점을 기준으로 MST를 만드는 알고리즘이라서, 시작 정점을 발전소 위치으로 두고, MST를 만드는 것은 어떨까?란 아이디어였다.

 

문제는 MST를 만든다 해도, 그것이 정답일 것이란 보장이 없다. 차라리 정답이 확실하게 보장이 되는 다익스트라가 더 낫다.

 

예전에 해결했던 문제

결국 아이디어가 떠올리길 빌며 크루스칼 알고리즘을 바탕으로 MST 그래프를 그려보기로 한다.

크루스칼 알고리즘은 그리디적인 관점에서 작은 간선부터 살펴볼 때, 간선을 잇는 두 정점이 같은 집합일 때, 그 간선을 잇지 않고, 아니면 같은 집합으로 합친다.

 

그런데 이 문제는 같은 집합이 아님에도, 합치지 않는 경우가 있었다. 바로, 다른 두 집합이 이미, 발전소와 연결되어 있는 경우였다.

 

여기까지 생각을 하자, 이미 해결했던 문제가 떠올랐다. 심지어 이미 블로그에 포스팅한적도 있다.

https://sumserv.tistory.com/93

백준 1368: 물대기

위 문제는 개념을 전환해, 하나의 정점을 만들고 간선으로 연결하는 방식으로 바꾼 뒤에 MST를 만들어서 해결한 문제다.

즉, 이번의 문제도 비슷하게 해결할 수 있을거다. 심지어 더 쉽다. 위의 문제는 알고리즘에 들어가기 전에 정점, 간선을 만드는 과정이 필요한데, 이번 문제는 그냥 발전소끼리의 집합을 합치기만 하면 그만이다.

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

vector<pair<int, pair<int, int>>> edges;
int N, M, K, P[1001], E[1001], U, W, V, ans = 0;

int find(int a)
{
	if (a == P[a]) return a;
	return P[a] = find(P[a]);
}
void merge(int a, int b)
{
	a = find(a); b = find(b);
	if (a < b) swap(a, b);
	P[b] = a;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> K;
	for (int i = 0; i <= N; i++) P[i] = i;
	for (int i = 0; i < K; i++)
	{
		cin >> E[i];
		for (int idx = 0; idx < i; idx++)
			merge(E[idx], E[i]);
	}
	for (int i = 0; i < M; i++)
	{
		cin >> U >> V >> W;
		edges.push_back({ W, {U, V} });
	}
	sort(edges.begin(), edges.end());
	for (int i = 0; i < edges.size(); i++)
	{
		int cost = edges[i].first;
		int from = edges[i].second.first;
		int to = edges[i].second.second;
		if (find(from) != find(to))
		{
			merge(from, to);
			ans += cost;
		}
	}
	cout << ans << '\n';
}

역시 알고리즘을 많이 풀고, 복습을 하는 것이 중요하다는 생각을 가지게 하는 문제였다.