๐ฃ ๋ฌธ์ ์ดํด
์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๊ตฌํ ๋ค, ๋ง์์ ๋ ๊ฐ๋ก ๋ถํ ํ ์ ์๋๋ก ๋๋ก๋ฅผ ์ ๊ฑฐํ์ฌ ์ด ์ ์ง๋น๊ฐ ์ต์๊ฐ ๋๋๋ก ํ๋ฉด ๋๋ค.
์ด ๋ฌธ์ ๋ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ดํ๋ค.
๐ญ ํ์ด ๊ณผ์
์์ฑ ์ธ์ด: C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Road {
public:
int start, dest, weight;
Road(int start, int dest, int weight) {
this->start = start;
this->dest = dest;
this->weight = weight;
}
};
const int MAX = 1001;
int home_cnt, road_cnt;
vector<Road> roads;
vector<Road> survived_lines;
int parent[MAX] = {0, };
int depth[MAX] = {0, };
// ์ด๊ธฐ ์ค์
void initialize() {
for (int i = 0; i <= home_cnt; ++i) {
parent[i] = i;
depth[i] = 1;
}
}
// ๊ฐ์ค์น์ ๋ฐ๋ฅธ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
bool compare(const Road &l1, const Road &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 must_deleted = 0;
int result = 0;
cin >> home_cnt;
cin >> road_cnt;
for (int i = 0; i < road_cnt; ++i) {
int a, b, c;
cin >> a >> b >> c;
roads.push_back(Road(a, b, c));
}
// ๊ฐ์ค์น ๊ธฐ์ค ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
sort(roads.begin(), roads.end(), compare);
// parent, depth ๋ฐฐ์ด ์ด๊ธฐํ
initialize();
for (int i = 0; i < road_cnt; ++i) {
int start_root = findRoot(roads[i].start);
int dest_root = findRoot(roads[i].dest);
if (start_root != dest_root) {
result += roads[i].weight;
survived_lines.push_back(roads[i]); // ๊ฒฝ๋ก ํฌํจ
mergeTree(start_root, dest_root);
}
}
// ๋น์ฉ์ด ์ต๋์ธ ๊ฐ์ ์ ์ฐพ์์ ์ ๊ฑฐํ๋ฉด
// ์ต์ ์ง์ด ํ๋ ์ด์์ธ ๋ ๋ง์๋ก ๋ถํ ํ ์ ์๋ค.
for (int i = 0; i < survived_lines.size(); ++i) {
must_deleted = max(must_deleted, survived_lines[i].weight);
}
cout << result - must_deleted << endl;
return 0;
}
์ผ๋ฐ์ ์ธ ์ต์ ์ ์ฅ ํธ๋ฆฌ ๋ฌธ์ ์ ๋์ผํ์ง๋ง, ๊ฒฝ๋ก๋ฅผ ๋ฐ๋ก ์ ์ฅํ๋ค.
์ต์ ์ ์ฅ ํธ๋ฆฌ์ ๊ฐ์ ์ ํฉ์ ๊ตฌํ ๋ค, ๋ฐ๋ก ๊ตฌํด๋ ๊ฒฝ๋ก๋ค์์ ๋น์ฉ์ด ์ต๋์ธ ๊ฐ์ ์ ์ฐพ์์ ์ ๊ฑฐํ๋ฉด ๋๋ค.
๐ ๋ฐฐ์ด ์
๊ธฐ์กด MST๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ๋ค๊ณผ ๋น์ทํ์ง๋ง ๊ฐ๋จํ ์กฐ๊ฑด์ด ์ถ๊ฐ๋ ๋ฌธ์ ์๋ค.
๋ฌด๋ํ๊ฒ ํ ์ ์์์!!