백준 1922번 네트워크 연결

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

1922번: 네트워크 연결

 

최소신장트리 기본 문제입니다.

 

본인은 크루스칼 알고리즘과 프림 알고리즘으로 풀어보았습니다.

 

 

<크루스칼>

1. 그래프의 상태는 따로 저장해놓고(v에 저장하였습니다)

아무것도 연결되어있지 않은 상태에서 시작합니다.

 

2. 그래프의 간선을 가중치를 기준으로 오름차순 정렬합니다.

 

3. 가중치가 가장 작은 간선부터 연결합니다.

이때, 사이클이 생기지 않아야 합니다.

이를 위해서 유니온-파인드 기법을 이용합니다.

 

<크루스칼 코드>

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

struct point {
	int u, v, w;
};

int n, m;
int parent[100001];

vector<point> v;

bool cmp(const point &p1, const point &p2) {
	return p1.w < p2.w;
}

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

bool merge(int u, int v) {
	u = find(u);
	v = find(v);
    
	//이미 최소신장트리에 포함
	if (u == v) return false;

	parent[u] = v;
	return true;
}

int main() {
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		v.push_back({a, b, c});
	}
	sort(v.begin(), v.end(), cmp);

	int res = 0;
	for (int i = 0; i < v.size(); i++) {
		if (merge(v[i].u, v[i].v)) {
			res += v[i].w;
		}
	}
	printf("%d\n", res);
	return 0;
}

 

 

 

 

<프림>

현재 트리에서 가장 작은 가중치의 간선을 선택, 연결 (시작 노드는 임의로 정합니다.)

모든 노드를 포함할 때까지 반복.

 

1. 간선의 정보를 저장합니다.

 

2. 시작노드를 임의로 결정합니다.

 

3. 시작노드는 방문확정이므로 방문체크를 해줍니다.

 

4. 시작노드와 연결된 노드와 가중치를 우선순위큐에 넣어줍니다.

 

* 우선순위큐는 pair에 대해서는 가장 먼저 first를 기준으로 정렬을 합니다.

따라서 큐에 넣을 때, first와 second에 주의해서 넣어줍니다.

* greater<>는 오름차순 정렬을 해줍니다.

* 우선순위큐 참고 블로그

https://koosaga.com/9

STL priority queue 활용법

 

5. 이제 큐에 들어있는 노드 중 가중치가 가장 작은 것을 꺼내어 방문체크를 해주고

이 노드와 연결된 노드를 큐에 넣어줍니다.

(이렇게 함으로써 현재 트리와 연결된 노드를 모두 고려할 수 있게 됩니다.)

 

6. 큐가 빌때까지 반복합니다.

 

<프림 코드>

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

int n, m;

vector<pair<int, int>>v[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

int visit[1001];

void prim() {
	int res = 0;
	int start = 1;

	visit[start] = 1;

	for (int i = 0; i < v[start].size(); i++) {
		int next = v[start][i].first;
		int nextval = v[start][i].second;

		q.push(make_pair(nextval, next));
	}

	while (!q.empty()) {
		int now = q.top().second;
		int nowval = q.top().first;
		q.pop();

		if (visit[now] == 1) continue;
		visit[now] = 1;
		res += nowval;

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i].first;
			int nextval = v[now][i].second;

			q.push(make_pair(nextval, next));
		}
	}

	printf("%d\n", res);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}

	prim();

	return 0;
}