글 읽기 - c++ DFS로 접근했으나 계속 틀립니다.

jja08111 3년 전 0

초기에 2 2 4 와 같은 경우 왼쪽으로 옮겼을 때 8 0 0 이 나오는 코드를 잘못 작성하여 지금은 isCombined 라는 변수를 만들어 이 부분은 해결했습니다.

하지만 코드를 제출해 보니 계속 틀렸다고 나옵니다...

고수분들 도와주십셔...

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N=20;

enum { UP=0, DOWN, LEFT, RIGHT };

int n,ret;

void up(vector<vector<int> >& board)
{
    for(int x=0;x<n;++x)
    {
        bool isCombined=false;
        for(int y=1;y<n;++y)
        {
            int ny=y, nx=x;
            // 숫자를 이동할 수 있을 때 까지 한 칸씩 이동한다.
            while(ny>0 && board[ny-1][nx]==0)
            {
                board[ny-1][nx]=board[ny][nx];
                board[ny][nx]=0;
                --ny;
            }
            // 숫자가 합쳐질 수 있는 경우
            if(!isCombined && ny>0 && board[ny][nx]==board[ny-1][nx])
            {
                board[ny-1][nx]=board[ny][nx]*2;
                board[ny][nx]=0;
                isCombined=true;
            }
            else if(board[ny][nx]!=0)
                isCombined=false;
        }
    }
}

void down(vector<vector<int> >& board)
{
    for(int x=0;x>=0;--x)
    {
        bool isCombined=false;
        for(int y=n-1;y<n;++y)
        {
            int ny=y, nx=x;
            // 숫자를 이동할 수 있을 때 까지 한 칸씩 이동한다.
            while(ny<n-1 && board[ny+1][nx]==0)
            {
                board[ny+1][nx]=board[ny][nx];
                board[ny][nx]=0;
                ++ny;
            }
            // 숫자가 합쳐질 수 있는 경우
            if(!isCombined && ny<n-1 && board[ny][nx]==board[ny+1][nx])
            {
                board[ny+1][nx]=board[ny][nx]*2;
                board[ny][nx]=0;
                isCombined=true;
            }
            else if(board[ny][nx]!=0)
                isCombined=false;
        }
    }
}

void left(vector<vector<int> >& board)
{
    for(int y=0;y<n;++y)
    {
        bool isCombined=false;
        for(int x=1;x<n;++x)
        {
            
            int ny=y, nx=x;
            // 숫자를 이동할 수 있을 때 까지 한 칸씩 이동한다.
            while(nx>0 && board[ny][nx-1]==0)
            {
                board[ny][nx-1]=board[ny][nx];
                board[ny][nx]=0;
                --nx;
            }
            // 숫자가 합쳐질 수 있는 경우
            if(!isCombined && nx>0 && board[ny][nx]==board[ny][nx-1])
            {
                board[ny][nx-1]=board[ny][nx]*2;
                board[ny][nx]=0;
                isCombined=true;
            }
            else if(board[ny][nx]!=0)
                isCombined=false;
        }
    }
}

void right(vector<vector<int> >& board)
{
    for(int y=0;y>=0;--y)
    {
        bool isCombined=false;
        for(int x=n-2;x<n;++x)
        {
            int ny=y, nx=x;
            // 숫자를 이동할 수 있을 때 까지 한 칸씩 이동한다.
            while(nx<n-1 && board[ny][nx+1]==0)
            {
                board[ny][nx+1]=board[ny][nx];
                board[ny][nx]=0;
                ++nx;
            }
            // 숫자가 합쳐질 수 있는 경우
            if(!isCombined && nx<n-1 && board[ny][nx]==board[ny][nx+1])
            {
                board[ny][nx+1]=board[ny][nx]*2;
                board[ny][nx]=0;
                isCombined=true;
            }
            else if(board[ny][nx]!=0)
                isCombined=false;
        }
    }
}

// 배열에서 최대 원소의 값을 반환
int getMaxVar(vector<vector<int> >& board)
{
    int maxNum=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            maxNum=max(maxNum,board[i][j]);
    return maxNum;
}
int counter=0;
void update(vector<vector<int> > board, int count)
{
    
    if(count==5)
    {
        ret=max(ret,getMaxVar(board));
        return;
    }

    for(int i=0;i<4;++i)
    {
        vector<vector<int> > next=board;
        switch(i)
        {
        case UP: up(next); break;
        case DOWN: down(next); break;
        case LEFT: left(next); break;
        case RIGHT: right(next); 
        }
        
        update(next,count+1);
    }
}

int main()
{
    cin>>n;
    vector<vector<int> > board(n,vector<int>(n,0));
    for(int y=0;y<n;++y)
        for(int x=0;x<n;++x)
        {
            cin>>board[y][x];
            ret=max(ret,board[y][x]);
        }
    
    update(board,0);
    cout<<ret<<endl;
    return 0;
}

jja08111 3년 전 0

제가 군인이라 연등에 시간에 쫓기며 코드를 작성해 아래와 같은 어이없는 코드를 작성했습니다.

바로 반복문이 이상하게 돌아가고 있는 부분입니다. 위쪽은 제대로 구현 했으나 나머지 방향은 모두 엉뚱하게 작성했습니다.

잘못 되어있는 부분을 주석 처리 했습니다.

//~~~~ 생략 ~~~~~
void down(vector<vector<int> >& board)
{
    //for(int x=0;x>=0;--x)
    for(int x=0;x<n;++x)
    {
        bool isCombined=false;
        //for(int y=n-1;y<n;++y)
        for(int y=n-2;y>=0;--y)
        {
            int ny=y, nx=x;
            // 숫자를 이동할 수 있을 때 까지 한 칸씩 이동한다.
            while(ny<n-1 && board[ny+1][nx]==0)
            {
                board[ny+1][nx]=board[ny][nx];
                board[ny][nx]=0;
                ++ny;
            }
            // 숫자가 합쳐질 수 있는 경우
            if(!isCombined && ny<n-1 && board[ny][nx]==board[ny+1][nx])
            {
                board[ny+1][nx]=board[ny][nx]*2;
                board[ny][nx]=0;
                isCombined=true;
            }
            else if(board[ny][nx]!=0)
                isCombined=false;
        }
    }
}

// ~~~~ 생략 ~~~~

void right(vector<vector<int> >& board)
{
    //for(int y=0;y>=0;--y)
    for(int y=0;y<n;++y)
    {
        bool isCombined=false;
        //for(int x=n-2;x<n;++x)
        for(int x=n-2;x>=0;--x)
        {
            int ny=y, nx=x;
            // 숫자를 이동할 수 있을 때 까지 한 칸씩 이동한다.
            while(nx<n-1 && board[ny][nx+1]==0)
            {
                board[ny][nx+1]=board[ny][nx];
                board[ny][nx]=0;
                ++nx;
            }
            // 숫자가 합쳐질 수 있는 경우
            if(!isCombined && nx<n-1 && board[ny][nx]==board[ny][nx+1])
            {
                board[ny][nx+1]*=2;
                board[ny][nx]=0;
                isCombined=true;
            }
            else if(board[ny][nx]!=0)
                isCombined=false;
        }
    }
}
// ~~~~ 생략 ~~~~

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

문제

문제

출처

ICPC

c++ DFS로 접근했으나 계속 틀립니다.

jja08111 3년 전 0

jja08111 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말