글 읽기 - 1번코드와 2번코드의 차이가 궁금합니다. (메모리 초과)

kdo6301 1년 전 0

1번 코드는 AC된 코드고, 2번 코드는 메모리 초과뜨는데

차이점은 check를 어디에서 해주냐의 차이인데 왜 메모리초과가 뜨는지 궁금합니다..

/* 1번코드입니다 (AC)
*/

int bfs(int y,int x)
{
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(y,x),make_pair(0,0)));
    check[y][x][0] = true;

    while(!q.empty())
    {   
        // ( 현재 y좌표 , 현재 x좌표 , 현재 horse moving 사용횟수, 현재 총 동작 수)
        int y = q.front().first.first;
        int x = q.front().first.second;
        int hm = q.front().second.first;
        int ans = q.front().second.second;

        q.pop();

        if(y==h-1 && x==w-1)
        {   
            return ans;
        }


        // 일반 동작 (상하좌우)
        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny>=0 && nx>=0 && nx<w && ny<h)
            {   
                // 다음좌표 (nx,ny)에 특정동작 사용하지않고 일반동작을 사용하여 방문해보지 않았으면 방문해본다.
                if(check[ny][nx][hm]==false && v[ny][nx]==0)
                {                                                  // 총 동작횟수
                    q.push(make_pair(make_pair(ny,nx),make_pair(hm,ans+1)));
                    
                    // (nx,ny)좌표에 총 특정동작 hm번 사용해서 방문 
                    check[ny][nx][hm] = true;

                }
            }
        }


        // 특정 동작 (홀스 무빙) 최대 k번 사용가능 
        if(hm<k)
        {
            for(int i=0;i<8;i++)
            {
                int ny = y + hdy[i];
                int nx = x + hdx[i];

                if(ny>=0 && nx>=0 && nx<w && ny<h)
                {   
                    // 다음 좌표 ny,nx에 특정동작 사용하여 이동하지 않았으면 이동해본다.
                    if(check[ny][nx][hm+1]==false && v[ny][nx]==0)
                    {   
                                                                         //총 동작 횟수 
                        q.push(make_pair(make_pair(ny,nx),make_pair(hm+1,ans+1)));
                         
                        // (nx,ny)좌표에 총 특정동작+1번 사용해서 방문함
                        check[ny][nx][hm+1] = true;
                    }
                }
            }
        }
    }


    // 목적지에 도달하지 못한경우 -1 리턴
    return -1;
}



/* 2번코드입니다 (메모리초과)
*/

int bfs(int y,int x)
{
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(y,x),make_pair(0,0)));

    while(!q.empty())
    {   
        int y = q.front().first.first;
        int x = q.front().first.second;
        int hm = q.front().second.first;
        int ans = q.front().second.second;

        check[y][x][hm] = true;

        q.pop();

        if(y==h-1 && x==w-1)
        {   
            return ans;
        }

        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny>=0 && nx>=0 && nx<w && ny<h)
            {   
                if(check[ny][nx][hm]==false && v[ny][nx]==0)
                {                                               
                    q.push(make_pair(make_pair(ny,nx),make_pair(hm,ans+1)));
                }
            }
        }

        if(hm<k)
        {
            for(int i=0;i<8;i++)
            {
                int ny = y + hdy[i];
                int nx = x + hdx[i];

                if(ny>=0 && nx>=0 && nx<w && ny<h)
                {   
                    
                    if(check[ny][nx][hm+1]==false && v[ny][nx]==0)
                    {   
                                           
                        q.push(make_pair(make_pair(ny,nx),make_pair(hm+1,ans+1)));
                    }
                }
            }
        }
    }

    return -1;
}

peydihalta 1년 전 2

미리 체크를 해 주지 않고 꺼낼 때만 체크하면, 이미 큐에 들어간 엘레먼트들이 꺼내질 때까지 체크되지 않아 동일한 엘레먼트들이 큐에 들어가게 됩니다.

kdo6301 1년 전 0

이해했습니다 답변 감사합니다!!!!!!!

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

문제

문제

출처

ICPC

1번코드와 2번코드의 차이가 궁금합니다. (메모리 초과)

kdo6301 1년 전 0

peydihalta 1년 전 2

kdo6301 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말