[C] 2048 (easy)

백준 12100번!

 

문제랑 코드도 너무 길고 사진도 많아서 이번 문제는 코드랑 풀이만ㅎㅎ

 

#include <stdio.h>
 
int N,ans=0;
 
int board_orig[25][25];
 
int dx[4] = {0,1,-1,0};
int dy[4] = {1,0,0,-1};
 
void printBoard(int board[25][25]){
    //debug
    for(int i = 0 ; i <= N+1 ; i++){
        for(int j = 0 ; j <= N+1 ; j++){
            printf("%d ",board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
 
void dfs(int cnt, int board[25][25]){
    // char tmp;
    // scanf("%c",&tmp);
    //printf("%d\n",cnt);
 
    for(int i = 1 ; i <= N ; i++){
            for(int j = 1 ; j <= N ; j++){
                if(board[i][j]>ans) ans = board[i][j];
            }
    }
    
    if(cnt==5){
        return;
    }
 
    int check[25][25];
    int board_copy[25][25];
    for(int i = 0 ; i <= N+1 ; i++){
        for(int j = 0; j <= N+1 ; j++) {
            check[i][j]=0;
            board_copy[i][j] = board[i][j];
        }
    }
 
    bool moved = false;
 
    // 위로 올릴때 
    for(int j = 1 ; j <= N ;j++){
       for(int i = 1 ; i<= N ; i++){
           if(board_copy[i][j]!=0){
                int to = i;
                while(to>0 && board_copy[to-1][j]==0){
                    to--;
                }
 
                // 합쳐지는 경우
                if(board_copy[i][j]==board_copy[to-1][j]&&!check[to-1][j]){
                    board_copy[to-1][j] *= 2;
                    check[to-1][j] = 1;
                    board_copy[i][j] = 0;
                    moved = true;
                } // 이동한 경우
                else if(to!=i){
                    board_copy[to][j] = board_copy[i][j];
                    board_copy[i][j] = 0;
                    moved = true;
                }
                //printBoard(board_copy);
           }
       }
    }
    if(moved){
        // printf("up\n");
        // printBoard(board);
        // printBoard(board_copy);
        dfs(cnt+1, board_copy);
    }
 
    for(int i = 0 ; i <= N+1 ; i++){
        for(int j = 0; j <= N+1 ; j++) {
            check[i][j]=0;
            board_copy[i][j] = board[i][j];
        }
    }
 
    moved = false;
 
     // 아래로 내릴때  
    for(int j = 1 ; j <= N ;j++){
       for(int i = N ; i>=1 ; i--){
           if(board_copy[i][j]!=0){
                int to = i;
                while(to<=N && board_copy[to+1][j]==0){
                    to++;
                }
 
                // 합쳐지는 경우
                if(board_copy[i][j]==board_copy[to+1][j]&&!check[to+1][j]){
                    board_copy[to+1][j] *= 2;
                    check[to+1][j] = 1;
                    board_copy[i][j] = 0;
                    moved = true;
                } // 이동한 경우
                else if(to!=i){
                    board_copy[to][j] = board_copy[i][j];
                    board_copy[i][j] = 0;
                    moved = true;
                }
                //printBoard(board_copy);
           }
       }
    }
    if(moved){
        // printf("down\n");
        // printBoard(board);
        // printBoard(board_copy);
        dfs(cnt+1, board_copy);
    }
 
    for(int i = 0 ; i <= N+1 ; i++){
        for(int j = 0; j <= N+1 ; j++) {
            check[i][j]=0;
            board_copy[i][j] = board[i][j];
        }
    }
 
    moved = false;
 
    // 왼쪽으로 밀 때
    for(int i = 1 ; i <= N ;i++){
       for(int j = 1 ; j<= N ; j++){
           if(board_copy[i][j]!=0){
                int to = j;
                while(to>0 && board_copy[i][to-1]==0){
                    to--;
                }
 
                // 합쳐지는 경우
                if(board_copy[i][j]==board_copy[i][to-1]&&!check[i][to-1]){
                    board_copy[i][to-1] *= 2;
                    check[i][to-1] = 1;
                    board_copy[i][j] = 0;
                    moved = true;
                } // 이동한 경우
                else if(to!=j){
                    board_copy[i][to] = board_copy[i][j];
                    board_copy[i][j] = 0;
                    moved = true;
                }
                //printBoard(board_copy);
           }
       }
    }
    if(moved){
        // printf("left\n");
        // printBoard(board);
        // printBoard(board_copy);
        dfs(cnt+1, board_copy);
    }
 
    for(int i = 0 ; i <= N+1 ; i++){
        for(int j = 0; j <= N+1 ; j++) {
            check[i][j]=0;
            board_copy[i][j] = board[i][j];
        }
    }
 
    moved = false;
 
    // 오른쪽으로 밀 때
    for(int i = 1 ; i <= N ;i++){
       for(int j = N ; j>=1 ; j--){
           if(board_copy[i][j]!=0){
                int to = j;
                while(to<=N && board_copy[i][to+1]==0){
                    to++;
                }
 
                // 합쳐지는 경우
                if(board_copy[i][j]==board_copy[i][to+1] && !check[i][to+1]){
                    board_copy[i][to+1] *= 2;
                    check[i][to+1] = 1;
                    board_copy[i][j] = 0;
                    moved = true;
                } // 이동한 경우
                else if(to!=j){
                    board_copy[i][to] = board_copy[i][j];
                    board_copy[i][j] = 0;
                    moved = true;
                }
           }
       }
    }
    if(moved){
        // printf("right\n");
        // printBoard(board);
        // printBoard(board_copy);
        dfs(cnt+1, board_copy);
    }
}
 
int main(){
    scanf("%d",&N);
    for(int i = 0 ; i <= N+1 ; i++) board_orig[i][0] = -1;
    for(int i = 0 ; i <= N+1 ; i++) board_orig[i][N+1] = -1;
    for(int i = 0 ; i <= N+1 ; i++) board_orig[0][i] = -1;
    for(int i = 0 ; i <= N+1 ; i++) board_orig[N+1][i] = -1;
    for(int i = 1 ;i <= N ; i++){
        for(int j = 1 ; j <= N ; j++) scanf("%d",&board_orig[i][j]);
    }
    dfs(0,board_orig);
    printf("%d\n",ans);
}

 

디버깅하는 코드까지 넣었더니 200줄이 넘는 코드ㅋㅋㅋ

디버깅 어떻게 했는지 궁금하신 분들이 있을까봐 안지웠다

방향이 네개만 있는 경우에는 index 복잡하게 쓰는거보다 그냥 손으로 고치는게 빠른거같다

특히 이문제는 for문으로 하려면 엄청 힘들거같다

첨에 for문으로 해보려고 dx,dy를 넣어뒀는데 안지웠네..

 

풀면서 든 생각들 정리

 

1. board를 입력받을 때 벽을 처리해주려고 -1을 넣었다, 첨에는 index 범위로만 체크할려고 했는데 합쳐지는지 아닌지 여부를 판단할때 편하게 하려고 그냥 벽을 세워줬다

2. 맵 크기도 작고 최대 이동 횟수도 5번이라 인자로 배열 전부 넘겨주는 형식으로 짜야겠다고 생각했다

3. dfs 함수에서 호출을 안하고 위,아래,왼쪽,오른쪽으로 잘 움직이는지 확인했다, 이때 체크배열은 만들어놓고 안썼는데도 잘 돌아가길래 안썼더니 나중에 필요했다ㅠㅠ

4. 안움직이는 경우에는 dfs 호출 안해줬는데 아마 호출해도 시간초과는 안 날듯하다

5. 시뮬레이션 코드는 어떻게 짜야 깔끔할까.....