๐ฃ ๋ฌธ์ ์ดํด
์ปดํจํฐ๋ฅผ ๋ ธ๋๋ก, ์ ์ฐ๊ฒฐ์ ๊ฐ์ ์ผ๋ก ๋ณด๊ณ ์ฃผ์ด์ง ๊ทธ๋ํ์์ ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST)์ ํฉ์ ๊ตฌํ๋ ๋ฌธ์ ์๋ค.
ํ์ ๋ฐ๋์์ง๋ง 1197๋ฒ ์ต์ ์คํจ๋ ํธ๋ฆฌ ์ ๊ทธ๋ฅ ๋์ผํ๊ฒ ํ๋ฆฌ๋ ๋ฌธ์ ์ด๋ค.
ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ/ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ ๋ ๊ฐ์ง ๋ฐฉ๋ฒ์ผ๋ก ํ ์ ์๋ค.
์ด ๋ฌธ์ ๋ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ดํ๋ค.
๐ญ ํ์ด ๊ณผ์
์์ฑ ์ธ์ด: C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Line {
public:
int start, dest, weight;
Line(int start, int dest, int weight) {
this->start = start;
this->dest = dest;
this->weight = weight;
}
};
const int MAX = 1001;
int com_cnt, line_cnt;
vector<Line> lines;
int parent[MAX] = {0, };
int depth[MAX] = {0, };
// ์ด๊ธฐ ์ค์
void initialize() {
for (int i = 0; i <= com_cnt; ++i) {
parent[i] = i;
depth[i] = 1;
}
}
// ๊ฐ์ค์น์ ๋ฐ๋ฅธ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
bool compare(const Line &l1, const Line &l2) {
return l1.weight < l2.weight;
}
// root ๋
ธ๋ ์ฐพ๊ธฐ
int findRoot(int node) {
if (node == parent[node]) return node;
return parent[node] = findRoot(parent[node]);
}
// ํธ๋ฆฌ ํฉ๋ณ
void mergeTree(const int node1, const int node2) {
if (depth[node1] < depth[node2]) {
depth[node2] += depth[node1];
depth[node1] = 0;
parent[node1] = node2;
}else {
depth[node1] += depth[node2];
depth[node2] = 0;
parent[node2] = node1;
}
}
int main() {
int result = 0;
cin >> com_cnt;
cin >> line_cnt;
for (int i = 0; i < line_cnt; ++i) {
int a, b, c;
cin >> a >> b >> c;
lines.push_back(Line(a, b, c));
}
// ๊ฐ์ค์น ๊ธฐ์ค ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
sort(lines.begin(), lines.end(), compare);
// parent, depth ๋ฐฐ์ด ์ด๊ธฐํ
initialize();
for (int i = 0; i < line_cnt; ++i) {
int start_root = findRoot(lines[i].start);
int dest_root = findRoot(lines[i].dest);
if (start_root != dest_root) {
result += lines[i].weight;
mergeTree(start_root, dest_root);
}
}
cout << result << endl;
return 0;
}
๐ ๋ฐฐ์ด ์
์ฝ๋ฉ ํ ์คํธ์ ์ด๋ ค์ด ๋ฌธํญ๋ค ์ค ๊ผญ ํ ๋ฌธ์ ์ฉ์ ์ต๋จ ๊ฒฝ๋ก ํ์ ๋๋ ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST)์ ๊ด๋ จ๋ ๋ฌธ์ ๊ฐ ๋์ค๊ณค ํ๋ค.
์๊ณ ๋ฆฌ์ฆ ์์ ๊ณผ์ ๋ก Kruskal, Prim ์๊ณ ๋ฆฌ์ฆ์ ์ ํ๋ฉด์ ๋ฐฑ์ค์ผ๋ก ์ฐ์ตํ๊ฒ ๋ค๋ ์๊ฐ์ผ๋ก ํ์ด๋ณด์๋ค.
DFS, BFS ๋ฌธ์ ๋ฅผ ํ์๋ ๊ฒ์ฒ๋ผ ์ด ์ ํ์ด ์ต์ํด์ง ๋๊น์ง ๋ค์ํ๊ฒ ํ์ด๋ด์ผ๊ฒ ๋ค!!!
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ๊ฐ์ฅ ๋จผ ๋ ธ๋ / ์ต๋จ ๊ฒฝ๋ก, ๋ค์ต์คํธ๋ผ (0) | 2020.11.21 |
---|---|
[BOJ] ๋ฐฑ์ค 1647 ๋์ ๋ถํ ๊ณํ / ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST), ํฌ๋ฃจ์ค์นผ (0) | 2020.11.20 |
[BOJ] ๋ฐฑ์ค 14503 ๋ก๋ด ์ฒญ์๊ธฐ / ๊ตฌํ (0) | 2020.11.06 |
[BOJ] ๋ฐฑ์ค 2606 ๋ฐ์ด๋ฌ์ค / ๋๋น ์ฐ์ ํ์(BFS) (0) | 2020.11.05 |
[2020 KAKAO BLIND RECRUITMENT] ๋ฌธ์์ด ์์ถ (0) | 2020.09.01 |