글 읽기 - 메모리초과가 왜 발생할까요?

jinny9650 2년 전 0

입력받은 map 배열에 지나온 경로를 '0'으로 바꾸면서 bfs를 진행하면 메모리 초과가 발생하게 됩니다.(주석처리 안된 코드)

하지만, visited 이차원 배열을 하나 더 만들어서 지나온 경로를 true로 설정하면서 bfs를 진행하면 답이 맞게 나옵니다.(주석처리된 코드)

두 방법에 무슨 차이가 있어서 하나는 메모리 초과가 발생하는 걸까요..?

#include <iostream>
#include <algorithm>
#include <queue>

struct pair {
    int first;
    int second;
    int move;
};

char map[102][102];
int N,M;

int delta[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

void bfs(int col,int row,int k) {
    std::queue<pair> Q;
    Q.push({col,row,k});

    while(!Q.empty()) {
        col=Q.front().first;
        row=Q.front().second;
        k=Q.front().move;
        if(col==N&&row==M) {
            std::cout << k;
            return;
        }
        map[col][row]='0';
        Q.pop();
        for(int i=0;i<4;++i) {
            int ncol=col+delta[i][0];
            int nrow=row+delta[i][1];
            if(map[ncol][nrow]=='1') {
                Q.push({ncol,nrow,k+1});
            }
        }
    }
}

int main() {

    std::cin >> N >> M;
    for(int i=1;i<=N;++i) {
        for(int j=1;j<=M;++j) {
        std::cin >> map[i][j];
        }
    }

    bfs(1,1,1);

    return 0;
}

/*
#include <iostream>
#include <algorithm>
#include <queue>

struct pair {
    int first;
    int second;
    int move;
};

char map[102][102];
int N,M;
bool visited[102][102];
int delta[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

void bfs(int col,int row,int k) {
    std::queue<pair> Q;
    Q.push({col,row,k});
    visited[col][row]=true;
    while(!Q.empty()) {
        col=Q.front().first;
        row=Q.front().second;
        k=Q.front().move;
        if(col==N&&row==M) {
            std::cout << k;
            return;
        }
        Q.pop();
        for(int i=0;i<4;++i) {
            int ncol=col+delta[i][0];
            int nrow=row+delta[i][1];
            if(!visited[ncol][nrow]&&map[ncol][nrow]=='1') {
                visited[ncol][nrow]=true;
                Q.push({ncol,nrow,k+1});
            }
        }
    }
}

int main() {

    std::cin >> N >> M;
    for(int i=1;i<=N;++i) {
        for(int j=1;j<=M;++j) {
        std::cin >> map[i][j];
        }
    }

    bfs(1,1,1);

    return 0;
}
*/

srand 2년 전 1

if(map[ncol][nrow]=='1') {
    Q.push({ncol,nrow,k+1});
}

18, 34번째 줄 Q 에 넣을 때 중복해서 넣을 수 있습니다.

Q.push 이후

map[ncol][nrow] = '0'

을 추가해서 중복해서 Q에 넣지 않도록 해주시면 됩니다.

혹은 map 변수의 값을 따로 써야 한다면, 주석처리 된 것처럼 별도 변수를 만들어 중복 push 하지 않도록 하시면 됩니다.

jinny9650 2년 전 0

오!! 해결됐습니다

선생님 감사합니다!!

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

문제

문제

출처

ICPC

메모리초과가 왜 발생할까요?

jinny9650 2년 전 0

srand 2년 전 1

jinny9650 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말