글 읽기 - 메모리초과를 해결할 방법이 궁금합니다.

icosang 1년 전 0

다음과 같이 코드를 짤 때, Edge E가 너무 많아 메모리가 모자란다는 것은 알겠으나, 어떤 식으로 대응해야 할 지 감이 안옵니다.

도움 부탁드립니다.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#define MAX_SIZE 100007

using namespace std;

int parent[MAX_SIZE];

struct Point {
    int x, y, z;
    Point(int a, int b, int c) {
        x = a, y = b, z = c;
    }
    bool operator<(Point B) {
        return x + y +z < B.x + B.y + B.z;
    }
};

struct Edge {
    int x, y;
    int value;
    Edge(int a, int b, int c) {
        x = a, y = b, value = c;
    }
    bool operator<(Edge b) {
        return value < b.value;
    }
};

int Find(int x, bool findScale = false) {
    if (parent[x] < 0) {
        if (findScale) return -parent[x];
        return x;
    }
    else {
        if (findScale) return Find(parent[x], true);

        int y = Find(parent[x]);
        parent[x] = y;
        return y;
    }
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);

    if (x == y)
        return;

    if (parent[x] < parent[y]) {
        parent[x] += parent[y];
        parent[y] = x;
    }
    else {
        parent[y] += parent[x];
        parent[x] = y;
    }
    return;
}

int main() {
    int a;
    int sum = 0;
    scanf("%d", &a);

    vector<Point> P;
    vector<Edge> E;
    memset(parent, -1, sizeof(parent));

    for (int i = 0; i < a; i++) {
        int b, c, d;
        scanf("%d %d %d", &b, &c, &d);
        P.push_back(Point(b, c, d));
    }

    bool sorted = false;

    for (int j = 0; j < a; j++) {
        for (int k = j + 1; k < a; k++) {
            int dist = min({ abs(P[j].x - P[k].x), abs(P[j].y - P[k].y), abs(P[j].z - P[k].z) });

            E.push_back(Edge(j, k, dist));
        }
    }

    sort(E.begin(), E.end());

    for (int j = 0; j < E.size(); j++) {
        if (Find(E[j].x) != Find(E[j].y)) {
            sum += E[j].value;
            Union(E[j].x, E[j].y);
        }
    }

    printf("%d", sum);
}

zenith82114 1년 전 13

간선을 (x, y, z) 벡터로 나타낼 때 간선의 길이가 min(x, y, z)이기 때문에

간선들을 x가 작은 순으로 정렬했을 때 순위가 N등 이하인 간선은

최소신장트리를 만들 때 사용될 가능성이 없어서 제외시킬 수 있습니다.

트리에는 정확히 N-1개 간선만 필요하기 때문입니다.

y로 정렬했을 때, z로 정렬했을 때도 마찬가지이므로

간선 O(N^2)개가 아니라 O(3N)개만 가지고 시작할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리초과를 해결할 방법이 궁금합니다.

icosang 1년 전 0

zenith82114 1년 전 13

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말