글 읽기 - 7576 메모리 초과 문제

jopemachine 4년 전 0

코드에서 메모리 초과가 발생하는 이유를 모르겠습니다.. ㅠㅠ

queue<pair<int,int>>때문인가요?

그렇다면 queue를 어떻게 고쳐야 메모리 초과가 안 날까요?

#include <iostream>
#include <queue>
#include <memory.h>

using namespace std;

queue<pair<int, int>> que;

void bfs(int** map, int** dist, int MAX_X, int MAX_Y){

    while(!que.empty()){

        int x = que.front().second;
        int y = que.front().first;

        // Up
        if(y - 1 >= 0    && map[y-1][x] == 0){
            que.push({y-1, x});
            map[y-1][x]  = 1;
            dist[y-1][x] = dist[y][x] + 1;
        }

        // Down
        if(y + 1 < MAX_Y && map[y+1][x] == 0){
            que.push({y+1, x});
            map[y+1][x]  = 1;
            dist[y+1][x] = dist[y][x] + 1;
        }

        // Left
        if(x - 1 >= 0    && map[y][x-1] == 0){
            que.push({y, x-1});
            map[y][x-1]  = 1;
            dist[y][x-1] = dist[y][x] + 1;
        }

        // Right
        if(x + 1 < MAX_X && map[y][x+1] == 0){
            que.push({y, x+1});
            map[y][x+1]  = 1;
            dist[y][x+1] = dist[y][x] + 1;
        }

        que.pop();
    }

}

int main() {
    // 2 ≤ M,N ≤ 1,000
    int    N,   M;
    cin >> N >> M;

    int** dist;
    int** map;

    for (int i = 0; i < M; i++) {
        map  = new int*[M];
        dist = new int* [M];

        for (int j = 0; j < N; j++) {
            map[j]  = new int[N];
            dist[j] = new int[N];
            memset(map[j] , 0, sizeof(int) * N);
            memset(dist[j], 0, sizeof(int) * N);
        }
    }

    bool allTomatoRipes = true;
//    queue<pair<int, int>> inputQue;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            if     (map[i][j] == 1){
                // {y, x}
                que.push({i, j});
                dist[i][j] = 1;
            }
            else if(map[i][j] == 0){
                allTomatoRipes = false;
            }
        }
    }

    if(!allTomatoRipes) {

        bfs(map, dist, N, M);

        int maxDist = dist[0][0];
        bool isPossible = true;

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {

                if (maxDist < dist[i][j]) {
                    maxDist = dist[i][j];
                }

                if (dist[i][j] == 0 && map[i][j] == 0) {
                    isPossible = false;
                    break;
                }
            }
        }

        if (isPossible) {
            cout << maxDist - 1;
        } else {
            cout << -1;
        }


    }
    else{
        cout << 0;
    }
}

djm03178 4년 전 1

57번째 줄부터 67번째 줄까지를 잘 살펴보세요.

    for (int i = 0; i < M; i++) { // M번의 루프를 돌면서 O(M)
        map  = new int*[M]; // M번의 루프를 돌면서 map에 M개의 int* 을 할당하고 O(M^2)
        dist = new int* [M]; // M번의 루프를 돌면서 dist에 M개의 int* 을 할당하고 O(M^2)

        for (int j = 0; j < N; j++) {
            map[j]  = new int[N]; // M번의 루프를 돌면서 map의 M개의 원소에 N개의 int를 할당하고 O(M^2*N)
            dist[j] = new int[N]; // M번의 루프를 돌면서 dist의 M개의 원소에 N개의 int를 할당하고 O(M^2*N)
            memset(map[j] , 0, sizeof(int) * N);
            memset(dist[j], 0, sizeof(int) * N);
        }
    }
    // map이랑 dist 자체는 O(NM)개의 원소만 있으면 되는데, O(NM)개의 원소를 M번 만들고 있으니 당연히 메모리 초과입니다.

jopemachine 4년 전 0

제가 이상한 실수를 했네요ㅠ

답변 정말 감사합니다!

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

문제

문제

출처

ICPC

7576 메모리 초과 문제

jopemachine 4년 전 0

djm03178 4년 전 1

jopemachine 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말