[코드트리] 3차원 평면 위의 점 C++

문제

https://www.codetree.ai/missions/9/problems/point-on-a-three-dimensional-plane?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

const int MAX_N = 100'000;

int n;
int uf[MAX_N+1];
vector<tuple<int,int,int,int> > points; // points: i번 점의 좌표{x, y, z, i}
vector<tuple<int,int,int> > edges; // a와 b번 점을 잇는 간선의 길이 diff {diff, a, b};

int myFind(int x){
    if(uf[x]==x) return x;
    return uf[x]=myFind(uf[x]);
}
void myUnion(int x, int y){
    x=myFind(x), y=myFind(y);
    if(x==y) return;
    uf[x]=y;
}

bool cmpSec(tuple<int,int,int,int> &v1, tuple<int,int,int,int> &v2){
    return get<1>(v1)<get<1>(v2);
}
bool cmpThr(tuple<int,int,int,int> &v1, tuple<int,int,int,int> &v2){
    return get<2>(v1)<get<2>(v2);
}

void makeEdges(){
    // x 좌표를 기준으로 정렬한 후, 인접 노드 간의 간선 저장
    sort(points.begin(), points.end());
    for(int i=0; i<n-1; ++i){
        int ax, ay, az, a;
        tie(ax, ay, az, a)=points[i];
        int bx, by, bz, b;
        tie(bx, by, bz, b)=points[i+1];

        // 임의의 두 개의 점을 연결할 때 드는 비용
        // 두 점의 x좌표의 차, 두 점의 y좌표의 차, 두 점의 z좌표의 차 중 가장 작은 값
        int min_diff=min({abs(ax-bx), abs(ay-by), abs(az-bz)});
        edges.push_back({min_diff, a, b});
    }

    // y 좌표를 기준으로 정렬한 후, 인접 노드 간의 간선 저장
    sort(points.begin(), points.end(), cmpSec);
    for(int i=0; i<n-1; ++i){
        int ax, ay, az, a;
        tie(ax, ay, az, a)=points[i];
        int bx, by, bz, b;
        tie(bx, by, bz, b)=points[i+1];

        // 임의의 두 개의 점을 연결할 때 드는 비용
        // 두 점의 x좌표의 차, 두 점의 y좌표의 차, 두 점의 z좌표의 차 중 가장 작은 값
        int min_diff=min({abs(ax-bx), abs(ay-by), abs(az-bz)});
        edges.push_back({min_diff, a, b});
    }

    // z 좌표를 기준으로 정렬한 후, 인접 노드 간의 간선 저장
    sort(points.begin(), points.end(), cmpThr);
    for(int i=0; i<n-1; ++i){
        int ax, ay, az, a;
        tie(ax, ay, az, a)=points[i];
        int bx, by, bz, b;
        tie(bx, by, bz, b)=points[i+1];

        // 임의의 두 개의 점을 연결할 때 드는 비용
        // 두 점의 x좌표의 차, 두 점의 y좌표의 차, 두 점의 z좌표의 차 중 가장 작은 값
        int min_diff=min({abs(ax-bx), abs(ay-by), abs(az-bz)});
        edges.push_back({min_diff, a, b});
    }
}

int main() {
    // [input] 점의 개수 n
    cin >> n;
    // [input] n개의 줄에 걸쳐 각 점의 좌표가 한 줄에 하나씩
    for(int i=0; i<n; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        points.push_back({x, y, z, i});
    }

    // [solution] 1. 간선 구하기
    makeEdges();
    // [solution] 2. 간선 정렬
    sort(edges.begin(), edges.end());
    // [solution] 3. uf 배열 초기화
    for (int i = 0; i <= n; ++i) {
        uf[i] = i;
    }
    // [solution] 4. Union-find
    int answer =0;
    for(auto e : edges){
        int diff, a, b;
        tie(diff, a, b)=e;
        if(myFind(a)==myFind(b)) continue;
        myUnion(a, b);
        answer+=diff;
    }

    // [output] answer 출력
    cout << answer << '\n';
    return 0;
}

 

메모리 초과 코드

모든 정점에 대해 간선을 만들었더니 메모리 초과가 났다.

x, y, z 각각 축으로 정렬했을때 가까운 정점들끼리만 간선을 연결해주어야 함.

+ uf 배열을 초기화 하지 않았음...

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

const int MAX_N = 100'000;

int n;
int uf[MAX_N+1];
vector<tuple<int,int,int> > points; // points[i]: i번 점의 좌표{x, y, z}
vector<tuple<int,int,int> > edges; // a와 b번 점을 잇는 간선의 길이 diff {diff, a, b};

int myFind(int x){
    if(uf[x]==x) return x;
    return uf[x]=myFind(uf[x]);
}
void myUnion(int x, int y){
    x=myFind(x), y=myFind(y);
    if(x==y) return;
    uf[x]=y;
}

int main() {
    // [input] 점의 개수 n
    cin >> n;
    // [input] n개의 줄에 걸쳐 각 점의 좌표가 한 줄에 하나씩
    for(int i=0; i<n; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        points.push_back({x, y, z});
    }

    // [solution] 1. 모든 점에 대해 간선 정보 구하기
    // i번 점과 j번 점의 좌표 차 중 가장 작은 값을 edges에 저장
    for(int i=0; i<n; ++i){
        for(int j=i+1; j<n; ++j){
            int ax, ay, az;
            tie(ax, ay, az)=points[i];
            int bx, by, bz;
            tie(bx, by, bz)=points[j];

            // 임의의 두 개의 점을 연결할 때 드는 비용
            // 두 점의 x좌표의 차, 두 점의 y좌표의 차, 두 점의 z좌표의 차 중 가장 작은 값
            int min_diff=min({abs(ax-bx), abs(ay-by), abs(az-bz)});
            edges.push_back({min_diff, i, j});
        }
    }

    // 간선 정렬
    sort(edges.begin(), edges.end());

    //Union-find
    int answer =0;
    for(auto e : edges){
        int diff, a, b;
        tie(diff, a, b)=e;
        if(myFind(a)==myFind(b)) continue;
        myUnion(a, b);
        answer+=diff;
    }

    cout << answer << '\n';
    return 0;
}

 

 

깔끔하게 코드 개선

[방법 1] 기존 방법-> cmp함수로 정렬하는 부분을 람다 함수+반복문으로 변경

[방법 2] Point를 클래스로 만들기+간선 추가하는 부분(반복되는 코드)를 함수로 만들기 void push(Point p1, Point p2)