https://www.acmicpc.net/problem/2887
이 문제의 경우 일반 크루스칼을 이용하여 모든 행성간의 거리를 계산해서 하려고 하다보니 메모리 초과가 발생하였다.
이 문제의 경우 해결방식은 행성의 x,y,z 좌표를 추출한 후 각각의 Vector에 저장한뒤 해당 Vector를 정렬해준 후 차이를 계산하여 그 값을 바탕으로 크루스칼 알고리즘을 돌리는 것이었다
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
vector<pair<int, pair<int, int>>> inputData;
int parent[100001];
vector<pair<int, int>> v[3];
int n;
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() {
cin >> n;
int tmp1, tmp2, tmp3;
for (int i = 0; i < n; i++) {
cin >> tmp1 >> tmp2 >> tmp3;
v[0].push_back({ tmp1,i });
v[1].push_back({ tmp2,i });
v[2].push_back({ tmp3,i });
}
sort(v[0].begin(), v[0].end());
sort(v[1].begin(), v[1].end());
sort(v[2].begin(), v[2].end());
int cost = 0;
for (int i = 0; i < n - 1; i++)
{
inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
}
sort(inputData.begin(), inputData.end());
for (int i = 0; i < n; 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;
}
}
cout << cost;
}전체 코드는 이렇게 된다 일단 크루스칼의 기본 함수는 알것이라 생각하고 설명을 생략한다
for (int i = 0; i < n; i++) {
cin >> tmp1 >> tmp2 >> tmp3;
v[0].push_back({ tmp1,i });
v[1].push_back({ tmp2,i });
v[2].push_back({ tmp3,i });
}자 이코드는 사용이유가 우리는 어차피 x간의 차와 y간의 차가 z간의 차가 가장 작은것을 이용해서 문제를 해결할것이므로 이렇게 각각 분리해서 인풋받는다 i는 vertex의 번호다
그후 정렬을 해주는데 정렬을 하면 각좌표별로 크기별로 정렬이 될것이므로 무조건 나의 다음 vertex와의 거리가 연결 cost가 될거이다 다음다음꺼는 봐줄필요가 없는게 어차피 x값기준으로 만 연산을 할건데 멀리 있으면 연산 할필요가 없기 때문이다
이이후는 일반 크루스칼과 같다
for (int i = 0; i < n - 1; i++)
{
inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
}이런식으로 vertex간 x거리 y거리 z거리를 넣는데 나의 다음거와의 거리만 넣어서 최솟값만 넣는다 중복이 나중에 발생해도 우리는 이 inputData를 정렬할거기 때문에 무조건 짧은 거와 연결된다
'백준(코테준비) > 그래프' 카테고리의 다른 글
| 백준 2252 / CPP / 위상 정렬 (1) | 2024.12.01 |
|---|---|
| 백준 4386 / C++ (0) | 2024.08.04 |
| 백준 1647 / C++ (0) | 2024.08.04 |
| 백준 1922 (0) | 2024.07.27 |
| 백준 1197 (0) | 2024.07.27 |
