JUMPGAME bfs로 푸는데 런타임에러가 뜹니다...

  • universalee
    universalee

    동적계획법이 아닌 bfs로 풀어봤는데 런타임에러(SIGKILL)가 뜹니다.
    메모리초과로 추측된다는데 이 코드에 메모리초과가 날 여지가 있나요?

    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <vector>
    using namespace std;
    
    typedef struct _POINT{
        int x,y;
    }Point;
    
    int n;
    int board[100][100];
    
    bool bfs(Point& sp)
    {
        bool ret=false;
        queue<Point> q;
        q.push(sp);
        while(!q.empty())
        {
            Point p=q.front();
            q.pop();
            if((p.x==n-1)&&(p.y==n-1))
            {
                ret=true;
                break;
            }
            Point p1,p2;
            p1.x=0,p1.y=0;
            p2.x=0,p2.y=0;
            int nx1=p.x+board[p.x][p.y],ny1=p.y;
            if(nx1<n&&ny1<n)
            {
                p1.x=nx1,p1.y=ny1;
                q.push(p1);
            }
            int nx2=p.x,ny2=p.y+board[p.x][p.y];
            if(nx2<n&&ny2<n)
            {
                p2.x=nx2,p2.y=ny2;
                q.push(p2);
            }
        }
        return ret;
    }
    
    int main() {
        int C;
        scanf("%d",&C);
        while(C!=0)
        {
            --C;
            memset(board,0,sizeof(board));
            scanf("%d",&n);
            for(int i=0; i<n; ++i)
            {
                for(int j=0; j<n; ++j)
                {
                    scanf("%d",&board[i][j]);
                }
            }
            Point sp;
            sp.x=0,sp.y=0;
            if(bfs(sp)) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }
    


    6달 전
3개의 댓글이 있습니다.
  • rumble99
    rumble99

    제 생각엔 배열 크기보다 더 큰 주소를 참조해서 런타임 에러가 나는거 같습니다.
    문제를 보니 N값이 <= 100 으로 되어있는데,
    현재 질문자님의 코드를 보면 board판이 100 * 100 으로 되어 있습니다.
    이럴경우 N값이 100이 들어오게 되면 런타임 에러가 나게 됩니다.
    101 * 101로 한 번 해보시길 바랍니다.


    6달 전 link
  • universalee
    universalee

    답변 감사드립니다. 101 넣어도 같은 에러가 뜨네요 ㅠㅠ 아무래도 bfs로는 이 문제가 안풀리는걸까요? 이 문제에 허용되는 메모리가 제법 크던데...


    6달 전 link
  • universalee
    universalee

    해결했습니다. 다음에 방문해야 할 점의 발견여부를 알려주는 배열을 필요하지 않다고 생각해서 쓰지 않았는데 중복발견되어서 큐에 들어가는 점이 메모리 초과의 원인이 되었던 것 같습니다. 이렇게 쉬운 걸 고민하고 있었네요 ㅜㅜ


    6달 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.