글 읽기 - c++] 메모리 초과 질문...

mimmyum 6년 전 0

어떤 부분에서 메모리 초과가 나는지 모르겠네요... 배열 크기때문이가 싶어서 class table을 매 테스트 케이스마다 생성/ 소멸 해줬는데...

다른 테스트 케이스들은 다 잘 나옵니다... 뭐가 문제일까요..

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


using namespace std;

typedef struct point{
    int x, y;
}POINT;

class Table{
    char **map;
    vector<POINT> Fires;
    vector<POINT> Man;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,-1,1};
    int w, h;

public:
    int move; //움직인 횟수
    Table(int w, int h);
    ~Table();
    void inputMap(int x, int y, char *c);
    void moveFire();
    int moveMan();
};

Table::Table(int w, int h){
    this->w = w;
    this->h = h;
    map = (char**)malloc(sizeof(char*)*h);
    for(int i = 0;i < h; i++){
        map[i] = (char*)malloc(sizeof(char)*w);
    }
}

Table::~Table(){
    Fires.clear();
    Man.clear();
    delete[] map;
    w = 0; h = 0;
}

void Table::inputMap(int x, int y, char *c){
    POINT tp;
    this->map[x][y] = *c;
    tp.x = x; tp.y = y;
    if(*c == '*'){
        Fires.push_back(tp);
    }
    else if(*c == '@'){
        Man.push_back(tp);
    }
}

void Table::moveFire() {
    vector<POINT>::iterator it;
    vector<POINT> newList;
    POINT tempPoint;
    int nowx, nowy;
    for(it = Fires.begin(); it != Fires.end(); ++it){
        for(int i = 0;i < 4; i++){
            nowx = (*it).x + dx[i];
            nowy = (*it).y + dy[i];
            if(nowx < 0 || nowx >= this->h || nowy < 0 || nowy >= this->w){
                continue;
            }

            if(map[nowx][nowy] == '.'){
                map[nowx][nowy] = '*';
                tempPoint.x = nowx;
                tempPoint.y = nowy;
                newList.push_back(tempPoint);

            }
        }
    }
    this->Fires = newList;

}

int Table::moveMan(){
    vector<POINT>::iterator it;
    vector<POINT> newList;
    POINT tempPoint;
    int nowx, nowy;
    for(it = Man.begin(); it != Man.end(); ++it){
        for(int i = 0;i < 4; i++){
            nowx = (*it).x + dx[i];
            nowy = (*it).y + dy[i];
            if(nowx < 0 || nowx >= this->h || nowy < 0 || nowy >= this->w){
                this->move = 1;
                return 1;
            }

            if(map[nowx][nowy] == '.'){
                tempPoint.x = nowx;
                tempPoint.y = nowy;
                newList.push_back(tempPoint);

            }
        }
    }
    if(newList.empty()){
        this->move = -1;
        return -1;
    }else {
        this->Man = newList;
        this->move = 0;
        return 0;
    }
}


int main(){
    std::ios::sync_with_stdio(false);
    int T;
    Table *table;
    char temp;
    int moving= 0;
    //scanf("%d\n",&T);
    cin >> T;
    for(int t = 0; t<T;t++){
        moving =0;
        int w=0, h=0;
        //scanf("%d %d\n",&w,&h);
        cin >> w >> h;
        table = new Table(w,h); //Table new table(w,h);
        for(int i = 0; i<h; i++){
            for(int j = 0; j<w; j++){
                //scanf("%c",&temp);
                cin>>temp;
                (*table).inputMap(i,j,&temp);
            }
        }

        //(*table).printMap();


        do{
            moving++;
            (*table).moveFire();
            (*table).moveMan();
            if((*table).move == 1){
                //printf("%d\n",moving);
                cout << moving << endl;
                break;

            }
            else if((*table).move == -1){
                //printf("IMPOSSIBLE\n");
                cout << "IMPOSSIBLE" << endl;
                break;
            }
        }while((*table).move == 0);

        delete table;

    }
    return 0;
}

bupjae 6년 전 0

메모리 할당은 malloc를 사용하고 있는데 메모리 반납은 delete[]를 사용하고 있습니다.

이는 잘못된 프로그램이며, C++ 표준에 의하면 이 프로그램의 결과는 정의되어 있지 않습니다. (Undefined Behavior)

bupjae 6년 전 0

한 가지 더 추가하자면, 메모리를 할당할 때 각 row를 따로 할당받았다면 메모리를 반납할 때도 각 row를 따로 반납해야 합니다.

mimmyum 6년 전 0

아래와 같은 방식으로 row별 메모리 delete를 했는데도 메모리 초과가 나오네요...

제가 어디선가 메모리 접근을 잘못하고 있는걸까요..

Table::~Table(){
    Fires.clear();
    Man.clear();
    for(int i = 0; i<h; i++){
        delete[] map[i];
    }
    delete[] map;
    w = 0; h = 0;
}

bupjae 6년 전 0

메모리 할당도 new[] 로 하고 있나요?

mimmyum 6년 전 0

말씀해 주신거 보고 앗! 하고

동적할당 malloc 으로 했으니깐 malloc으로 할당한 부분은 모두 free로 다시 메모리 해제하도록 했는데

50%에서 다시 메모리초과가 뜨네요...OTL

@bupjae 님, 계속 도움 주셔서 감사합니다...

중간에 한번 움직인 다음의 내용을 newList에 옮겨담는게 문제일수도 잇다고 생각해서 일단 그거를 바꿔보도록 할게요..

mimmyum 6년 전 0

방식을 바꿔서 다시 풀었습니다....

클래스를 아예 안쓰고 다른방법으로 푸니깐 풀렸네요... 감사합니다 ...

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

문제

문제

출처

ICPC

c++] 메모리 초과 질문...

mimmyum 6년 전 0

bupjae 6년 전 0

bupjae 6년 전 0

mimmyum 6년 전 0

bupjae 6년 전 0

mimmyum 6년 전 0

mimmyum 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말