[1922] 네트워크 연결 - MST(Kruskal) ★☆☆ / 복습 ○

 

[ 문제 ] : https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

---

[ 문제 접근 ]

 

 

MST 의 풀이법으로는 Kruskal, Prim 두 가지 방법이 있다. 

​

-- < Kruskal > --

1. make-set ( 모든 노드들을 자기자신을 가리키게끔 배열 Parent을 초기화 한다.)

2. 가중치를 기준으로 입력 받은 간선들을 오름차순 한다.

3. cost가 적은 간선부터 하나씩 선택한다.

4. 선택된 간선의 개수가 n-1 개가 될때까지 find-union 작업 한다.

 

 

Kruskal 문제풀때 주의해야할 점이 있다.

---

보통의 그래프 문제를 풀때

vector<std::pair<int,int>> adjacent[1001]; 이렇게 엣지를 입력 받곤 하는데,

Kruskal 문제는 입력을 조금 다르게 받아야한다.엣지의 cost를 비교해야하기 때문에 그래프를 인접 리스트 형태로 받게 되면 sorting이 힘들어진다. 그래서 Kruskal은 아래와 같이 그래프 받는게 가장 편하다.

 

1. 구조체 ( class or struct ) 로 엣지를 받는다. ( 가장 선호 )

2. vector<pair<int,pair<int,int>>> 로 받는다 ( ex) BOJ_1197 )

3. vector<tuple<int,int,int>>로 받는다. ( tuple 파이썬에만 있는줄.. )

​

몇번 노드가 몇번 몇번에 연결되어있는지 보다 엣지 하나 하나의 cost 값을 봐야된다.

 

참고로 [프로그래머스] "섬 연결하기 문제"  는 문제 자체에서 vector<vector> 로 받는데, 문제를 보면 알테지만

vector<vector<int>> costs = { {0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8} }; 이런식으로 주어졌다.

그러니깐 costs[0]이 0번 노드고 costs[1]이 1번 노드가 아니라 cost[0] 은 1번 엣지 cost[1] 은 1번 엣지로 이해하는게 편하다.

---

 

---

[ 최종 코드 ( Kruskal) ]

#include<iostream>
#include<vector>
#include<algorithm>

using std::cout; using std::cin;
using std::vector;


// < Kruskal>
// 1.공집합에서 시작
// 2. make-set
// 3. 엣지들 오름차순 정렬
// 4. n-1이 될때까지 find- union 반복.

class Edge {
public:
	int node[2];
	int cost;
	Edge(int _a, int _b, int _cost) : cost(_cost) {
		node[0] = _a;
		node[1] = _b;
	}
	bool operator<(const Edge& e)const {
		return cost < e.cost;
	}
};

int n, m;

vector<Edge> edges;
int parent[1001];
int tree_size[1001];
int cost;


int  findSet(int x) {  
	if (parent[x] == x) return x;
	else {
		return findSet(parent[x]);
	}
}
void unionSet(int x,int y) {
	x = findSet(x); // x의 트리 사이즈를 찾아야하기 때문에 부모노드를 찾아야한다. 이걸 안하면 findSet도 오류나고 unionSet도 오류난다.
	y = findSet(y);
	if (tree_size[x] > tree_size[y]) {
		parent[y] = x;
		tree_size[x] += tree_size[y];
	}
	else {
		parent[x] = y;
		tree_size[y] += tree_size[x];
	}
}

int kruskal() {
	// make-set ( 부모를 모두 자기 자신으로 )
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	std::fill_n(tree_size, n + 1, 1);// unionSet을 할때 큰게 작은거 밑으로 들어가기위한 tree_size 배열 1로 초기화.
	sort(edges.begin(),edges.end());  // 엣지 자체가 정렬이 되어있어야한다.

	int cnt = 0;
	
	for (int i = 0; i < edges.size() && cnt < n - 1; i++) {  // i< m 으로 했다가 오류 났다 조심하자 입력 받을때 i-- 라서 i -1 되어있다.
		int x = edges[i].node[0];
		int y = edges[i].node[1];
		if (findSet(x) != findSet(y)) {
			unionSet(x, y);
			cnt++;
			cost += edges[i].cost;
		}
	}
	return cost;

}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	int a, b, c;
	edges.reserve(m);  // 
	while (m--) {
		cin >> a >> b >> c;
		edges.push_back(Edge(a, b, c));
	}
	
	cout << kruskal();

	return 0;
}

[ 코드 보기 ( Prim ) ▼ ]

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

constexpr auto INF = 1234567;

using std::cout; using std::cin;
using std::vector;


// < Prim >
// 모든 노드의 key값과 selected 값을 초기화한다.

int n, m, a, b, c;

vector<std::pair<int, int>> adjancent[1001];
int key[1001];  // key 값
bool selected[1001]; // 선택 됐는지.


int prim(int start){
	int answer = 0;

	// 모든 노드의 key값과 selected 값을 초기화한다.
	std::fill_n(key, n + 1, INF);

	// 시작점을 시작으로 선택 시작
	// key 값은 0으로 selected는 true 로
	key[start] = 0;
	selected[start] = true;

	// 모든 노드들이 선택될 때까지.
	int cnt = 1;
	int cur = start;
	while (cnt <= n - 1) {
		// 선택된 노드의 인접한 노드의 key값 변경 해주기.
		int next, cost;
		for (size_t i = 0; i < adjancent[cur].size(); i++) {
			
			next = adjancent[cur][i].first;
			cost = adjancent[cur][i].second;

			if (selected[next])continue;
			if (key[next] > cost) {
				key[next] = cost;
				}
			}
		// 아직 선택되지 않은 노드들 중에 key값이 가장 작은 노드 선택.
		int min_cost = INF;
		int min_idx = -1;
		for (size_t i = 1; i <= n; i++) {
			if (selected[i])continue;
			if (min_cost > key[i]) {
				min_cost = key[i];
				min_idx = i;
			}
		}
		cnt++; // 선택 됐으니깐 cnt 증가.
		answer += min_cost; 
		selected[min_idx] = true;	
	}

	return answer;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	while (m--) {
		cin >> a >> b >> c;
		adjancent[a].push_back({ b,c });
		adjancent[b].push_back({ a,c });
	}
	
	cout << prim(1);

	return 0;
}

 

보다시피 Kruskal 보다 채점 시간이 늘었났다.

위의 Prim 코드의 시간복잡도는 O(n^2)이기 때문이다.

 

그래서 보통 Prim 알고리즘을 구현할땐 Priority Queue 를 이용한다.

 

[ 코드 보기 ( Prim(2) ) ▼ ]

#include<iostream>
#include<vector>
#include<queue>

constexpr auto INF = 1234567;

using std::cout; using std::cin;
using std::vector; using std::pair;


// < Prim >
// 

int n, m, a, b, c;

vector<std::pair<int, int>> adjancent[1001];

bool visited[1001]; // 선택 됐는지.
struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) const{
		return a.second > b.second;
	}
};

int prim(int start){
	int answer = 0;
	std::priority_queue<pair<int, int>, vector<pair<int, int>>,cmp> pq;
	visited[start] = true;

	for (auto elem : adjancent[start]) {
		int start= elem.first;
		int start_key = elem.second;
		pq.push({ start,start_key });
	}

	while (!pq.empty()) {
		int cur = pq.top().first;
		int cur_cost = pq.top().second;
		pq.pop();

		if (!visited[cur]) {
			visited[cur] = true;
			answer += cur_cost;
			for (size_t i = 0; i < adjancent[cur].size(); i++) {
				int next = adjancent[cur][i].first;
				int next_key = adjancent[cur][i].second;
				if (visited[next]) continue;
				pq.push({ next,next_key });
			}
		}
			
	}

	return answer;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	while (m--) {
		cin >> a >> b >> c;
		adjancent[a].push_back({ b,c });
		adjancent[b].push_back({ a,c });
	}
	
	cout << prim(1);

	return 0;
}

---

[ Key Point ]

 

👉 Kruskal 알고리즘만 알고 있으면 어려움 없이 풀 수 있다.

 

👉 Prim 알고리즘은 priority queue 를 사용하여 시간복잡도를 줄인다.

---

[ 다른 사람 풀이 ]

 

ref : https://m.blog.naver.com/ndb796/221240353788