글 읽기 - 1753번 메모리 초과 질문드립니다!

js8662 3년 전 0

안녕하세요! 다익스트라 알고리즘으로 푸는 1753번 메모리 초과 질문 드립니다!

main에서 함수를 일일히 부르게 해서 visited와 dist 벡터를 일일히 만들어놨더니 메모리 초과 오류가 생기는 것 같더라고요,,,

dijkstra함수를 접속할 때마다 매번 visited와 dist 벡터를 생성해내지 않고,

c++의 stl vector 함수에서 vector visited와 dist를 매번 해당하는 false 와 INF로 초기화할 수 있는 함수 없을까요?(clear는 0으로 초과한다고 나와서 질문드립니다!)

아니면 iterator로 일일이 다 처리를 해야 할까요?

아니면 더 좋은 방법 있을까요?

감사합니다!!!!!!!!

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;

int N, M;
int INF = 0xfffffff;
vector<vector<int>> W;
vector<bool> visited;
vector<int> dist;
int dijkstra(int sta, int end) {

    visited = vector<bool>(N + 1, false);         //지나간 노드 체크하는 visited vector
    dist = vector<int> (N + 1, INF);               //거리 체크하는 dist vector

    for (int i = 1; i <= N; i++)                //dist에 시작 노드로 가중치 초기화
        dist[i] = W[sta][i];

    int vnear = sta;
    visited[sta] = true;                        //visited 출발 노드 체크

    for (int k = 0; k < N; k++) {
        int min_dist = INF;
        for (int i = 1; i <= N; i++) {          //for문으로 최소 거리 확인,
            if (!visited[i] && min_dist > dist[i]) {
                vnear = i;
                min_dist = dist[i];
            }
        }

        for (int i = 1; i <= N; i++) {
            if (visited[i] || W[vnear][i] == INF)
                continue;
            if (dist[vnear] + W[vnear][i] < dist[i])
                dist[i] = dist[vnear] + W[vnear][i];
        }
        visited[vnear] = true;
    }
    return dist[end];
}

int main(void) {
    int sta, end, cost, start;
    cin >> N >> M >> start;
    W = vector < vector<int> >(N + 1, vector<int>(N + 1, INF));
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &sta, &end, &cost);
        W[sta][end] = cost;
    }
    for (int k = 1; k <= N; k++) {
        if (k == start) {
            printf("0\n");
        }
        else if (dijkstra(start, k) == INF) {
            printf("INF\n");
        }
        else {
            printf("%d\n", dijkstra(start, k));
        }
    }
    return 0;
}

sait2000 3년 전 1

이 문제는 다익스트라를 한 번만 돌려서 푸는 문제입니다.

js8662 3년 전 0

한번으로 고쳤는데도 메모리 초과가 나네요....

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;

int N, M;
int INF = 0xfffffff;
vector<vector<int>> W;

void dijkstra(int sta) {

    vector<bool> visited = vector<bool>(N + 1, false);         //지나간 노드 체크하는 visited vector
    vector<int> dist = vector<int> (N + 1, INF);               //거리 체크하는 dist vector

    for (int i = 1; i <= N; i++)                //dist에 시작 노드로 가중치 초기화
        dist[i] = W[sta][i];

    int vnear = sta;
    visited[sta] = true;                        //visited 출발 노드 체크

    for (int k = 0; k < N; k++) {
        int min_dist = INF;
        for (int i = 1; i <= N; i++) {          //for문으로 최소 거리 확인,
            if (!visited[i] && min_dist > dist[i]) {
                vnear = i;
                min_dist = dist[i];
            }
        }

        for (int i = 1; i <= N; i++) {
            if (visited[i] || W[vnear][i] == INF)
                continue;
            if (dist[vnear] + W[vnear][i] < dist[i])
                dist[i] = dist[vnear] + W[vnear][i];
        }
        visited[vnear] = true;
    }

    for (int k = 1; k <= N; k++) {
        if (k == sta) {
            printf("0\n");
        }
        else if (dist[k] == INF) {
            printf("INF\n");
        }
        else {
            printf("%d\n",dist[k]);
        }
    }

}

int main(void) {
    int sta, end, cost, start;
    cin >> N >> M >> start;
    W = vector < vector<int> >(N + 1, vector<int>(N + 1, INF));
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &sta, &end, &cost);
        W[sta][end] = cost;
    }
    dijkstra(start);
    return 0;
}

js8662 3년 전 0

가중치가 10이하라고 해서 바꿔도 메모리 초과.............가 나네요ㅠㅠ

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;

int N, M;
int INF = 0xfffffff;
vector<vector<int>> W;

void dijkstra(int sta) {

    vector<bool> visited = vector<bool>(N + 1, false);         //지나간 노드 체크하는 visited vector
    vector<int> dist = vector<int> (N + 1, 10);               //거리 체크하는 dist vector

    for (int i = 1; i <= N; i++)                //dist에 시작 노드로 가중치 초기화
        dist[i] = W[sta][i];

    int vnear = sta;
    visited[sta] = true;                        //visited 출발 노드 체크

    for (int k = 0; k < N; k++) {
        int min_dist = INF;
        for (int i = 1; i <= N; i++) {          //for문으로 최소 거리 확인,
            if (!visited[i] && min_dist > dist[i]) {
                vnear = i;
                min_dist = dist[i];
            }
        }

        for (int i = 1; i <= N; i++) {
            if (visited[i] || W[vnear][i] == INF)
                continue;
            if (dist[vnear] + W[vnear][i] < dist[i])
                dist[i] = dist[vnear] + W[vnear][i];
        }
        visited[vnear] = true;
    }

    for (int k = 1; k <= N; k++) {
        if (k == sta) {
            printf("0\n");
        }
        else if (dist[k] == INF) {
            printf("INF\n");
        }
        else {
            printf("%d\n",dist[k]);
        }
    }

}

int main(void) {
    int sta, end, cost, start;
    cin >> N >> M >> start;
    W = vector < vector<int> >(N + 1, vector<int>(N + 1, 10));
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &sta, &end, &cost);
        W[sta][end] = cost;
    }
    dijkstra(start);
    return 0;
}

sait2000 3년 전 1

제가 보기엔 W가 문제인 것 같습니다. 정점이 2만개이면 W의 크기가 최소 int 4억개고 그러면 대략 1.5GB의 메모리입니다. 인접 행렬 말고 인접리스트와 우선 순위 큐를 이용한 다익스트라 알고리즘을 구현해 보세요. 우선 순위 큐를 안 사용하는 방법도 있긴 합니다만 아무튼 인접행렬을 사용할 순 없습니다.

sait2000 3년 전 1

https://www.acmicpc.net/board/view/34516

FAQ입니다. 참고하세요.

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

문제

문제

출처

ICPC

1753번 메모리 초과 질문드립니다!

js8662 3년 전 0

sait2000 3년 전 1

js8662 3년 전 0

js8662 3년 전 0

sait2000 3년 전 1

sait2000 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말