https://www.acmicpc.net/problem/1647
이 문제의 경우 최소 신장 트리 문제중 하나로 일단 최소 신장 트리를 만드는 알고리즘으로 크루스칼을 사용해서 풀었다
크루스칼 알고리즘 전전 게시물에 작성했다시피 경로의 Cost가 낮은 경로들 부터 연결을 하지만 서로의 root 가 다른 경로들 만 연결 하고 각자의 root들을 합쳐질때마다 업데이트 해주면 되는 문제 였다
이 문제에서는 핵심적으로 4개의로직이 있다.
1. 부모를 찾는 로직
int findParent(int x) {
if (parent[x] == x)
return x;
else return parent[x] = findParent(parent[x]);이 로직은 x의 부모 root를찾는 코드로 재귀적으로 부모를 찾으면서 부모를 업데이트도 해주는 코드이다
2. 같은 부모인지 찾는 로직
bool sameParent(int x, int y) {
x = findParent(x);
y = findParent(y);
if (x == y)
return true;
else
return false;
3. 2개의 다른 트리를 합치는 로직 합칠때는 합쳐진 트리의 부모만 바꿔주면 된다
void uni(int x, int y) {
x = findParent(x);
y = findParent(y);
parent[y] = x;
}
4. cost가 낮은 순 부터 오름차순으로 입력 데이터를 정렬 한다 그후 루프를 돌면서 2번 3번 과정을 반복해준다 그후 연결된 cost중 가장 높은부분을 뺴준다 그 이유는 이문제에서 마을을 두개로 분리한다고 하였으니 가장 비용이 많이 드는 길 을 없애면 된다
for (int i = 0; i < inputData.size(); i++) {
if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
uni(inputData[i].second.first, inputData[i].second.second);
cost += inputData[i].first;
cnt += 1;
if (cnt == v - 1) {
cost -= inputData[i].first;
}
}
}
전체 코드는 아래와 같다
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[100001] = { 0, };
int findParent(int x) {
if (parent[x] == x)
return x;
else return parent[x] = findParent(parent[x]);
}
bool sameParent(int x, int y) {
x = findParent(x);
y = findParent(y);
if (x == y)
return true;
else
return false;
}
void uni(int x, int y) {
x = findParent(x);
y = findParent(y);
parent[y] = x;
}
int main() {
int v, e;
long long cost;
cost = 0;
int cnt = 0;
cin >> v >> e;
int tmp1, tmp2, tmp3;
for (int i = 0; i < e; i++) {
cin >> tmp1 >> tmp2 >> tmp3;
inputData.push_back({ tmp3,{tmp1,tmp2} });
}
sort(inputData.begin(), inputData.end());
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
for (int i = 0; i < inputData.size(); i++) {
if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
uni(inputData[i].second.first, inputData[i].second.second);
cost += inputData[i].first;
cnt += 1;
if (cnt == v - 1) {
cost -= inputData[i].first;
}
}
}
cout << cost;
}'백준(코테준비) > 그래프' 카테고리의 다른 글
| 백준 2887 / C++ / 그래프 / 크루스 (0) | 2025.01.12 |
|---|---|
| 백준 2252 / CPP / 위상 정렬 (1) | 2024.12.01 |
| 백준 4386 / C++ (0) | 2024.08.04 |
| 백준 1922 (0) | 2024.07.27 |
| 백준 1197 (0) | 2024.07.27 |
