글 읽기 - BFS / C++ 메모리 초과 나요 ㅠㅠㅠㅠ

kongalyj 3년 전 0

메모리 초과가 왜 나는 건가요 ㅠㅠ

#include <stdio.h>
#include <queue>

using namespace std;

struct now{
    int g;
    int s;
    int cnt;
};

int main()
{
    queue <struct now> q;
    struct now current;
    char maze[102][102]={0};
    int n, m, i;
    scanf("%d %d", &n, &m);
    for(i=1;i<=n;i++){
        scanf("%s", &maze[i][1]);
    }
    q.push((struct now){1,1,0});
    while(q.size()!=0){
        current=q.front();
        if(current.g==m && current.s==n){
            printf("%d", current.cnt+1);
            return 0;
        }
        if(maze[current.s+1][current.g]=='1' && current.s+1<=n){
            q.push((struct now){current.g,current.s+1,current.cnt+1});
            maze[current.s][current.g]='0';
        }
        if(maze[current.s-1][current.g]=='1' && current.s-1>=1){
            q.push((struct now){current.g,current.s-1,current.cnt+1});
            maze[current.s][current.g]='0';
        }
        if(maze[current.s][current.g-1]=='1' && current.g-1>=1){
            q.push((struct now){current.g-1,current.s,current.cnt+1});
            maze[current.s][current.g]='0';
        }
        if(maze[current.s][current.g+1]=='1' && current.g+1<=m){
            q.push((struct now){current.g+1,current.s,current.cnt+1});
            maze[current.s][current.g]='0';
        }
        q.pop();
    }
}

exponential_e 3년 전 0

c++코드를 직접 제대로 돌려볼 수 없어서 일단 예상되는 문제점에 대해 말씀드립니다.

메모리 초과가 나는 이유는 방문한 지점에 대한 체크가 되지 않고 있는 것 같아보입니다. 이러한 경우 큐에 중복되는 경로가 담기게 되고 이러한 경우 큐의 메모리가 터졌기 때문인 것으로 예상됩니다.

이러한 탐색 문제는 기본적으로 이미 방문한 위치는 굳이 다시 방문하지 않아도 되기 때문에 다음 방문점을 큐에 담기 전 해당 방문 지점이 이미 방문했는지 체크를 해주셔야합니다.

아래와 같은 예제 입력에서 작성자님께선 (1, 1) 부터 순차적으로 탐색하길 바라고 코드를 짜셨겠지만,

실제로 동작은 (1, 1)을 담고 다음 정점은 (1, 2)가 담기게 됩니다.

여기까진 정상적이나 (1, 2)에서 다음 방문점을 찾을 때 (1, 1)이 방문했다는 표시가 되지 않았기 때문에 큐에는 다음 방문 정점으로 (1, 1), (1, 3)이 모두 담기게 됩니다.

위와 같은 경우 데이터가 작으면 작동하긴하나, 데이터가 조금만 커지면 큐 내부에 중복되는 정점이 여러번 들어가게 되고, 큐 메모리가 초과되는 현상이 발생합니다.

추가로 테스트해볼만한 데이터를 반복문으로 제공드릴테니 제대로 동작하는지 확인 부탁드립니다. (테스트해 볼 예제)

만약 로컬에서도 메모리초과 에러가 발생한다면 위에 말씀드린 문제가 맞는 것 같으니 방문하면서 방문했는지 여부에 대한 체크를 실시하는 코드를 작성 후 제출해보시기 바랍니다.

또한, 문제에 제공된 데이터와 제가 드린 예제로 직접 출력해보면서 디버깅을 해보시는 것이 어떤 중복이 발생하는지에 대해 이해하는데 도움이 되실 것 같습니다.

4 6
101111
101010
101011
111011
// ===================구분선=====================
    
// 테스트해 볼 예제
printf("%d %d", 100, 100);
for(int i = 0; i < 100; i++) {
    for(int j = 0; j < 100; j++) {
        printf("%d ",1);
    }
    printf("\n");
}

exponential_e 3년 전 1

아 정정 드립니다.

(1, 1) -> (2, 1) 순이고

그다음에 (2, 1)에서 큐에 담기는 정점은 (1, 1), (3, 1) 입니다.

dldyddlwl 3년 전 2

그리고,

scanf("%s", &maze[i][1]); 이 부분은 부적절합니다.

만약, 한 행씩 받으려고 하셨다면, scanf("%s", maze[i]), 가 적절한 표현입니다.

exponential_e 3년 전 0

아 예제 확인을 제대로 안 했네요. 죄송합니다.

반복문에 공백을 넣어뒀는데 수정해서 다시 드리니 해당 코드의 출력 결과를 이용해 테스트해보시길 바랍니다.

// 테스트해 볼 예제
printf("%d %d", 100, 100);
for(int i = 0; i < 100; i++) {
    for(int j = 0; j < 100; j++) {
        printf("%d", 1);
    }
    printf("\n");
}

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