-
[BOJ / C++] 1197번 : 최소 스패닝 트리Study (etc)/Problem Solving 2023. 9. 4. 16:58
문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
Solved.ac 레벨
골드 IV
풀이
MST(Minimum Spanning Tree; 최소 신장 트리 or 최소 스패닝 트리)의 가중치를 구하는 문제다.
최소 신장 트리란 최소 간선의 개수로 모든 노드를 연결한 트리를 말한다.
최소 간선의 개수는 노드 개수 - 1개이며 모든 노드의 루트 노드는 1번 노드로 동일하다.
최소 신장 트리를 구할 수 있는 여러 방법 중에 크루스칼 알고리즘을 이용했다.
크루스칼 알고리즘을 이용하기 위해서는 합집합을 구하는 알고리즘, Union-Find 알고리즘에 대한 학습이 선행되어야 한다.
나는 아래 동빈나님의 두 영상을 통해 Union-Find 알고리즘과 크루스칼 알고리즘을 학습했고, 이 문제의 풀이 그 자체가 된다.
단순히 MST의 가중치를 구하는 문제이기 때문이다.
Union-Find 알고리즘 크루스칼 알고리즘 Code
#include<bits/stdc++.h> using namespace std; int v, e, ans = 0; int parent[10001]; //부모 노드 탐색 int getParent(int x) { if(parent[x] == x) return x; return parent[x] = getParent(parent[x]); } //두 부모 노드를 합치기 void unionParent(int a, int b) { a = getParent(a); b = getParent(b); if(a < b) parent[b] = a; else parent[a] = b; } //같은 부모를 가지는지 확인 bool findParent(int a, int b) { a = getParent(a); b = getParent(b); if(a == b) return true; else return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> v >> e; vector<pair<int, pair<int, int>>> MAP(e); for(int i = 0; i < e; i++) { int a, b, c; cin >> a >> b >> c; MAP[i] = {c, {a, b}}; } for(int i = 1; i <= v; i++) { parent[i] = i; } sort(MAP.begin(), MAP.end()); for(int i = 0; i < e; i++) { int start = MAP[i].second.first; int end = MAP[i].second.second; int cost = MAP[i].first; if(!findParent(start, end)) { ans += cost; unionParent(start, end); } } cout << ans << "\n"; return 0; }
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
'Study (etc) > Problem Solving' 카테고리의 다른 글
[BOJ / C++] 1647번 : 도시 분할 계획 (0) 2023.09.05 [BOJ / C++] 1922번 : 네트워크 연결 (0) 2023.09.04 [BOJ / C++] 10610번 : 30 (0) 2023.09.02 [BOJ / C++] 1253번 : 좋다 (0) 2023.09.01 [BOJ / C++] 1806번 : 부분합 (1) 2023.08.31