백준 1197번 _최소 스패닝 트리

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

1197번: 최소 스패닝 트리

 

1. 풀이방법

 

 이 문제는 그리디적으로 풀어야 한다. 내가 한 풀이 순서대로 써보자면

 

1) 우선순위 큐에 간선의 데이터를 다넣고 cost가 작은 순서대로 나오도록 비교함수를 작성한다.

 

2) 우선순위 큐를 빼면서 연결이 안된 노드면 연결시키고, 연결이 이미 되었다면 넘어간다.

 

 여기서 아마 연결이 안된 노드면 연결시키고, 연결이 이미 되었다면 넘어간다. 이 부분을 어떻게 하는지가

가장 중요한데 여기서는 union - find 알고리즘을 사용하여 정점간의 연결여부를 파악한다.

 

---

 

2. union -find

 

 따로 포스팅할 계획이라서 가장 핵심이 되는 부분만 설명하겠다.

 

정점	1	2	3	4	5	6
(바로위) 부모	2	3	3	4	4	5

 

 이런 트리와 바로 상위부모의 데이터가 있는 배열이 있다고 하면 각 정점들의 연결유무를 어떻게 알수있을까?

 

 바로 자신의 정점의 최상위 부모가 누구인지를 알수있으면 된다.

 

 하나 예를 들자면 위에 표를 참고해서 1과 6의 연결여부를 살펴보면

 1의 부모 -> 2 -> 2의 부모 -> 3 -> 3의 부모 -> 3 자기 자신 

 6의 부모 -> 5 -> 5의 부모 -> 4 -> 4의 부모 -> 4 자기 자신

 그러니 1의 최상위 부모는 3, 6의 부모는 4이므로 연결이 되어있지않다. 

 

 이렇게 연결여부를 따져 구현하면 된다.

 

---

3. 코드 

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

class info
{
public:
	int u;
	int v;
	long long cost;
public:
	info(int u_in, int v_in, long long cost_in)
		:u(u_in), v(v_in), cost(cost_in)
	{}
};

struct cmp
{
	bool operator() (const info& a, const info& b)
	{
		//큐의 비교함수는 sort랑 반대
		return a.cost > b.cost;
	}
};

priority_queue<info, vector<info>, cmp> pri_que;
int v, e;
int parents[10002];

void parentsInit()
{
	for (int i = 1; i <= v; i++)
		parents[i] = i;
}

int getParent(int a)
{
	if (parents[a] == a) return a;
	return parents[a] = getParent(parents[a]);
}

//트리형태로 
void Union(int a, int b)
{
	a = getParent(a);
	b = getParent(b);
	parents[b] = a;
}

int main()
{
	cin >> v >> e;
	parentsInit();

	//간선 입력
	int a, b;
	long long c;
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;
		pri_que.push(info(a, b, c));
	}

	long long answer = 0;
	//간선 빼면서 연결됬는지 안됬는지 확인
	while (!pri_que.empty())
	{
		int u = pri_que.top().u;
		int v = pri_que.top().v;
		long long cost = pri_que.top().cost;
		pri_que.pop();

		//두간선이 연결이 안되어있을 때만 추가
		if (getParent(u) != getParent(v))
		{
			Union(u, v);
			answer += cost;
		}
	}
	cout << answer << endl;
	return 0;
}

 

---

 

4. 후기

 

최소 신장트리와 union -find 알고리즘을 학습하기에는 좋은 문제였다.

다만 지금짠 union -find 알고리즘은 최악의 경우에는 O(N)이 걸리기 때문에 최적화된 버전의 코드로도 한번 짜봐야겠다.