해설
MST(최소 신장 트리)를 구하는 문제이다.
최소 신장 트리를 구하는 문제는 크루스칼 알고리즘이나 프림 알고리즘을 이용하여 해결할 수 있는데, 그 중 크루스칼 알고리즘으로 해결하였다.
먼저, 정점을 잇는 간선을 길이가 짧은 순으로 나열한다.
간선을 탐색하면서 두 정점이 다른 그룹이면 두 정점을 하나의 그룹으로 합치고 해당 간선을 선택한다.
이미 두 정점이 같은 그룹에 있으면 패스한다.
크루스칼 알고리즘에 대한 자세한 설명은 최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘를 참조하면 좋다.
코드
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>
using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
#define X first
#define Y second
vector<iii> edge;
vector<int> nrank(100, 1);
vector<int> parent(100, 0);
void initialize(int n) {
for (int i=0; i<n; i++) parent[i] = i;
}
int find(int u) {
if (parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return ;
if (nrank[u] > nrank[v]) swap(u, v);
else if (nrank[u] == nrank[v]) nrank[v]++;
parent[u] = v;
}
void setGraph(const vector<vector<int>>& costs) {
for (auto v : costs)
edge.push_back({v[2], v[0], v[1]});
sort(edge.begin(), edge.end());
}
int solution(int n, vector<vector<int>> costs) {
setGraph(costs);
initialize(n);
int ans = 0;
for (auto [w, u, v] : edge) {
if (find(u) == find(v)) continue;
merge(u, v);
ans += w;
}
return ans;
}
'ㄴ 알고리즘 > 프로그래머스풀이' 카테고리의 다른 글
[프로그래머스 lv3] 자물쇠와 열쇠 (0) | 2022.09.12 |
---|---|
[프로그래머스 lv3] 경주로 건설 풀이 (0) | 2022.09.11 |
[프로그래머스 lv3] 스티커 모으기(2) 풀이 (0) | 2022.09.10 |
[프로그래머스 lv3] 디스크 컨트롤러 풀이 (0) | 2022.09.09 |
[프로그래머스 lv3] 기지국 설치 풀이 (0) | 2022.09.09 |
댓글