[G4] 백준 14950번 정복자 C++ 최소 스패닝 트리, MST

리뷰

 

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

시작 노드로 부터 모든 노드를 잇는 최소 가중치를 구하는 문제

 

 

전역 변수

• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• t : 정복 시 가중치를 저장할 변수
• Edge : 간선의 시작 노드 sn, 도착 노드 dn, 가중치 w를 정의할 구조체, w를 기준으로 오름차순 정렬한다.
• edges : 간선 정보를 저장할 Edge타입 벡터
• nodes : 노드가 속한 그룹 명을 저장할 배열

 

함수

1. Find

int Find(int a)

 

노드가 속한 그룹의 루트 노드 번호를 찾기 위한 함수

1. 매개 변수로 탐색을 할 노드 번호를 변수 a로 입력 받아준다.
2. 만약 nodes[a]가 a와 동일하다면 a를 리턴해 준다.
3. 아닐 경우 nodes[a]를 Find함수에 nodes[a]를 매개변수로 전달하여 리턴 받은 값을 저장해 주고, 이를 리턴한다.

 

문제풀이

1. n, m, t값을 입력 받아주고, n개의 노드 정보를 nodes 배열에 자기 자신으로 값을 갖도록 저장해 준다.
2. m개의 간선 정보를 입력 받아 edges벡터에 추가해 준다.
3. sort 메서드를 통해 edges벡터를 오름차순으로 정렬해 준다.
4. 변수 dist와 cnt를 0으로 초기화 해주고, 모든 간선을 순회해 준다.
5. 시작 및 종료 노드 sn, dn을 Find 함수의 매개변수로 전달해 각각 리턴 값을 A, B로 입력 받아준다.
6. 만약 A와 B가 같다면 이미 동일한 그룹에 속해 있는 것이므로 continue 처리해 준다.
7. 둘이 같은 그룹에 속해있지 않은 경우 nodes[B]의 값을 A로 변경해 그룹을 이어 준다.
8. 그룹이 합쳐진 경우 dist에 w + t * cnt만큼의 값을 더해주고 cnt를 증가시켜 준다.
9. 모든 탐색을 마친 후 dist에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 몇개의 노드가 연결 되었는지를 체크해 주어야 정복 비용 증가를 계산해 줄 수 있다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, t;
struct Edge {
	int sn, dn, w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};
vector<Edge> edges;
int nodes[100001];

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

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

	cin >> n >> m >> t;
	for (int i = 0; i < n; ++i) nodes[i] = i;
	while (m--) {
		int sn, dn, w; cin >> sn >> dn >> w;
		if (sn > dn) swap(sn, dn);
		edges.push_back({ sn, dn, w });
	}

	sort(edges.begin(), edges.end());
	int dist = 0;
	int cnt = 0;
	for (int i = 0; i < edges.size(); ++i) {
		const Edge& edge = edges[i];
		int sn = edge.sn, dn = edge.dn, w = edge.w;
		int A = Find(sn);
		int B = Find(dn);
		if (A == B) continue;
		nodes[B] = A;
		dist += w + t * cnt;
		cnt++;
	}
	cout << dist;
}