글 읽기 - 고수님들, 메모리 초과 도움 부탁드립니다.

dudgh9661 3년 전 0

메모리 초과가 뜨는데.. 256MB이면, 256 * 10^6이잖아요? 이 코드에서 메모리 초과가 나는 이유를 모르겠습니다. 대충 계산해봐도 200MB는 넘지 않는 것 같아서요 ㅠ

모두 short로 변경해도 메모리 초과가 납니다...

제가 공간 복잡도 계산을 잘못한거겠죠..? 고수님들 도와주시면 감사드리겠습니다.

아! 그리고, 이 문제를 BFS가 아닌, 이런식으로 풀면 로직상 틀린 것이 있나요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int row, col, height;
struct POS {
    int h, r, c;
};
vector<POS> tomato; //익은 토마토
vector<POS> updatingTomato; //익게 될 토마토

int map[100][100][100];
int UD[4] = {1, -1, 0, 0};
int LR[4] = {0, 0, 1, -1};
int FB[2] = {-1, 1}; //앞,뒤
void init() {
    cin >> col >> row >> height;
    int input;

    for (int h = 0; h < height; h++) {
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                cin >> input;
                map[h][r][c] = input; //높이, 행, 열
                if (input == 1) tomato.push_back({h, r, c});
            }
        }
    }
}

bool inRange(int h, int r, int c) {
    if (h < 0 || h >= height || r < 0 || r >= row || c < 0 || c >= col) return false;
    return true;
}

void Search() {
    //익은 토마토들을 기준으로, 익게 될 토마토들의 정보를 저장한다.
    for(int all = 0; all < tomato.size(); all++) {
        int ph = tomato[all].h;
        int pr = tomato[all].r;
        int pc = tomato[all].c;

        //4방향
        for (int i = 0; i < 4; i++) {
            int nr = pr + UD[i];
            int nc = pc + LR[i];
            if (!inRange(ph, nr, nc) || map[ph][nr][nc] != 0) continue;
            updatingTomato.push_back({ph, nr, nc});
        }
        //앞,뒤
        for (int i = 0; i < 2; i++) {
            int nh = ph + FB[i];
            if (!inRange(nh, pr, pc) || map[nh][pr][pc] != 0) continue;
            updatingTomato.push_back({nh, pr, pc});
        }
    }
}

bool isAllClear() {
    for (int h = 0; h < height; h++) {
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if( map[h][r][c] == 0 ) {
//                    cout << "안익은 토마토 존재!" << endl;
                    return false;
                }
            }
        }
    }
    return true;
}

void update() {
    for(int i = 0; i < updatingTomato.size(); i++) {
        map[updatingTomato[i].h][updatingTomato[i].r][updatingTomato[i].c] = 1;
    }
    tomato.clear();
    tomato.resize(0);
    tomato = updatingTomato; //익게 될 토마토들을 익은 토마토로 저장해준다.

    updatingTomato.clear(); //익게 될 토마토들을 모두 익게 해줬으므로 초기화.
    updatingTomato.resize(0);
}


int main() {
    int day = 0;
    init();
    while(1) {
        Search();
        if( updatingTomato.empty() ) {
//            cout << "더 이상 익을 토마토가 존재하지 않으므로, 모두 다 익었는지 확인" << endl;
            if( !isAllClear() ) day = -1;
//            if( isAllClear() ) cout << "모두 다 익었다" << endl;
//            else cout << "모두 다 익지 못함" << endl;
            break;
        }
        update();
        day++;
    }
    cout << day << endl;
    return 0;
}

djm03178 3년 전 1

BFS를 할 때는 큐에 넣기 전에 방문 표시를 해야 합니다. 큐에 넣은 뒤에 할 경우, 이미 큐에 중복된 원소들이 들어간 상태일 수 있습니다.

djm03178 3년 전 1

그리고 지금의 이 코드가 바로 BFS가 맞습니다.

dudgh9661 3년 전 0

메모리 초과가 나는 이유는 뭔가요??? 같은 곳을 계속 방문해서 일종의 무한루프에 빠졌기 떄문인가요?

djm03178 3년 전 1

어떤 정점이 두 번 큐에 들어갔다고 합시다. 그러면 두 번 뒤에는 그 정점으로부터 출발한 것들이 다시 한 번 한 정점에 모일 수 있고, 그러면 그 정점은 4번 큐에 들어가게 됩니다. 두 번 뒤에는 8번, 그 뒤에는 16번, ... 이렇게 늘어나다 보면 나중에는 한 순간에 큐에 별의 수보다도 많은 정점을 담으려고 하게 될 수도 있습니다.

dudgh9661 3년 전 0

아 .. 감사합니다! 이해했습니다. 말씀해주신 힌트 덕분에 통과하게 되었네요..

전 꼭 queue를 사용해서 구현해야만 BFS라고 생각했었네요.. 감사합니다.

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

문제

문제

출처

ICPC

고수님들, 메모리 초과 도움 부탁드립니다.

dudgh9661 3년 전 0

djm03178 3년 전 1

djm03178 3년 전 1

dudgh9661 3년 전 0

djm03178 3년 전 1

dudgh9661 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말