algospot   10달 전

다익스트라 경우는 힙자료구조를 구현해서 nlgn으로 한다손 치는데,

애초에 메모리초과가 발생하여, 다른 문제에서도 물었지만, vector을 안쓰고, 메모리초과를 막는 방법이 있을까요?

game2k   10달 전

2만*2만 = 4억 개의 공간중 실제로 간선 정보가 들어가는 공간은 30만개 입니다. 나머지는 사용되지 않는 공간이죠...

간선 정보만을 저장해보세요

algospot   10달 전

답변 감사합니다.


그럼 간선 정보를

typedef struct edgd {

             int st,ed;

             int cost;

};

edge e[300003];

이런 형태로 한다면, dijkstra 알고리즘 시, 해당 정점에 연결된 다른 정점과 그에 대한 비용을 찾을때, 모든 간선을 하나하나 뜯어봐야 하게 되지 않나요?

algospot   10달 전

vector를 써서 동적 접근 하는건 구현했습니다.

vector를 '안쓰고' 구현하는 걸 물었습니다..

game2k   10달 전

vector 를 안쓰고가 정확히 무슨 뜻인지 모르겠네요.

이 문제는 힙을 사용하지 않고 위에 작성하신 대로 최소거리를 구하면 메모리초과가 나지 않더라도 O(V^2) 정도가 소요되기 때문에 시간초과가 나게 됩니다.

algospot   10달 전

힙 자료구조를 쓴 다익스트라는 이미 구현해놓았습니다.

다만, 입력 받을때, vector를 쓰지 않고 메모리초과 안나게 받는 방법을 알고 싶은 겁니다..

위에 써놓은 코드는 그냥 예시로 짜놓은 거에요.

game2k   10달 전

vector가 가변길이 배열이니까  가변길이 배열의 역할을 할 수 있는 다른 자료구조를 사용하면 되지 않을까요?

#include <stdio.h>
#include <stdlib.h>
int V, E, K;
 
struct EDGE {
    int st, ed;
    int cost;
};
typedef struct EDGE edge;
edge e[300003];
int distance[20002];
int vertex[20002];
int check[20002];
void dijkstra(int st) {
    int i, j, min, idx;
    for (i = 1; i <= V; i++) check[i] = 0;
    for (i = 0; i <= V; i++) distance[i] = 300000;
    check[st] = 1;
    distance[st] = 0;
    for (i = 1; i <= vertex[st] - vertex[st-1]; i++) {
        distance[e[vertex[st - 1] + i - 1].ed] = e[vertex[st - 1] + i-1].cost;
    }
    while (1){
        min = 300000;
        for (j = 1; j <= V; j++) {   //이부분을 힙으로
            if (!check[j] && min>distance[j]) {
                min = distance[j];
                idx = j;
            }
        }
        if (min == 300000)
            break;
        check[idx] = 1;
        for (j = 1; j <= vertex[idx] - vertex[idx - 1]; j++) {
            int pt = vertex[idx - 1] + j - 1;
            if (!check[e[pt].ed] && distance[e[pt].ed]>min + e[pt].cost) {
                distance[e[pt].ed] = min + e[pt].cost;
            }
        }
    }
}
 
int cmp(const void* arg1, const void* arg2)
{
    edge* a = (edge*)arg1;
    edge* b = (edge*)arg2;
    return a->st < b->st ? -1 : a->st > b->st ? 1 : 0;
}
 
int main(void) {
    int i, j, a, b, c;
    scanf("%d%d", &V, &E);
    scanf("%d", &K);
    for (i = 0; i<E; i++) {
        scanf("%d%d%d", &a, &b, &c);
        e[i].st = a;
        e[i].ed = b;
        e[i].cost = c;
    }
    qsort(e, E, sizeof(edge), cmp);
    vertex[1] = 0;
    for (int i = 1, j = 0; i <= V; ++i) 
        for (; e[j].st == i; ++j)
            vertex[i]++;
    for (int i = 1; i <= V; ++i)
        vertex[i] += vertex[i - 1];
    dijkstra(K);
    for (i = 1; i <= V; i++) {
        if (distance[i] == 300000) printf("INF\n");
        else printf("%d\n", distance[i]);
    }
    return 0;
}

도움이 되었으면 좋겠습니다.

game2k   10달 전

#include <stdio.h>
#include <stdlib.h>
#define INF 987654321
int V, E, K;
 
struct EDGE {
    int st, ed;
    int cost;
};
typedef struct EDGE edge;
edge e[300003];
edge heap[300003];
 
int distance[20002];
int vertex[20002];
 
int size;
 
void push(edge e)
{
    int cur = ++size;
    while (cur != 1 && heap[cur / 2].cost > e.cost)
    {
        heap[cur] = heap[cur / 2];
        cur /= 2;
    }
    heap[cur] = e;
}
void pop()
{
    edge last = heap[size--];
    int cur = 1;
    int child = 2;
    while (child <= size)
    {
        if (child < size && heap[child].cost > heap[child + 1].cost) child++;
        if (last.cost <= heap[child].cost) break;
 
        heap[cur] = heap[child];
        cur = child;
        child *= 2;
    }
    heap[cur] = last;
}
 
void dijkstra(int st) {
    int i, j, here, cost, pt, there, weight;
    edge tmp;
    for (i = 0; i <= V; i++) distance[i] = INF;
    distance[st] = 0;
    tmp.st = st;
    tmp.cost = 0;
    push(tmp);
    while (size > 0) {
        here = heap[1].st;
        cost = heap[1].cost;
        pop();
        if (cost > distance[here])
            continue;
        for (j = 0; j < vertex[here] - vertex[here - 1]; j++)
        {
            pt = vertex[here - 1] + j;
            weight = e[pt].cost + cost;
            if (distance[e[pt].ed] > weight)
            {
                distance[e[pt].ed] = weight;
                tmp.st = e[pt].ed;
                tmp.cost = weight;
                push(tmp);
            }
        }
    }
}
 
int cmp(const void* arg1, const void* arg2)
{
    edge* a = (edge*)arg1;
    edge* b = (edge*)arg2;
    return a->st < b->st ? -1 : a->st > b->st ? 1 : 0;
}
 
int main(void) {
    int i, j, a, b, c;
    scanf("%d%d", &V, &E);
    scanf("%d", &K);
    for (i = 0; i<E; i++) {
        scanf("%d%d%d", &a, &b, &c);
        e[i].st = a;
        e[i].ed = b;
        e[i].cost = c;
    }
    qsort(e, E, sizeof(edge), cmp);
    vertex[1] = 0;
    for (int i = 1, j = 0; i <= V; ++i)
        for (; e[j].st == i; ++j)
            vertex[i]++;
    for (int i = 1; i <= V; ++i)
        vertex[i] += vertex[i - 1];
    dijkstra(K);
    for (i = 1; i <= V; i++) {
        if (distance[i] == INF) printf("INF\n");
        else printf("%d\n", distance[i]);
    }
    return 0;
}

algospot   10달 전

감사합니다 ^^

Edge list 라는게 있습니다.

int arr[M][2] 배열을 선언하고

간선의 start([M][0]) 번째를 기준으로 배열을 정렬합니다

그리고나서 N 크기의 int psum 배열의 i 인덱스에 i번째 start를 가지고 있는 간선의 개수를 저장합니다

psum[i] 는 start를 i로 하는 간선의 개수가 됩니다

그리고 그 배열의 0~N-1까지의 부분합을 다시 구합니다

그러면 psum[i]~(psum[i]-1) 이 노드 i가 가지고 있는 간선의 데이터 부분이 됩니다.

그러면 크기 M을 가진 간선 리스트가 완성됩니다.

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