C - 12100 2048(easy)

https://www.acmicpc.net/problem/12100

 

2~1024의 블럭이 20*20의 게임판내에 주어지고

이 경우에 5번 움직여서 얻을 수 있는 가장 큰 블럭의 수를 찾는 문제이다.

 

2048(easy)는 드래그 가능 횟수가 5로 충분히 작게 주어진다.

따라서 백트래킹 기법없이 통과가 된다. 그래서 easy이다.

이 문제를 통해 토대가 될 코드를 만들고 거기에 분기한정 백트래킹을 섞으면 2048(hard)를 풀 수 있다.

 

dfs는 각 단계에서 상하좌우로 드래그하며 다음 단계로 재귀를 통해 넘어가는 식으로 간단하게 구현하면된다.

신경써야할것은 2048게임 규칙에 따라 상하좌우로 이동시키는 방법이다.

 

한칸에 드래그 방향으로 같은 수를 가진 블럭이 있다면 2개의 블럭은 합쳐질 수 있고

한번 드래그에 한번 합쳐진 블럭은 다시 다른 블럭과 합쳐질 수 없다.

void move_up(int lv) {
    for(int i=0; i<size; i++) {
        cnt = 0;
        for(int j=0; j<size; j++) {
            if(board[lv][j][i] > 0) {
                if(cnt%2 == 0) { 
                    //빈칸
                    board[lv+1][cnt/2][i] = board[lv][j][i];
                } else if(board[lv+1][cnt/2][i] == board[lv][j][i]) {
                    //같은수
                    board[lv+1][cnt/2][i] += board[lv][j][i];
                } else {
                    //다른수
                    cnt++;
                    board[lv+1][cnt/2][i] = board[lv][j][i];
                }
                cnt++;
            }
        }
    }
}

 

언어를 코드로 구현하면 위와같다. 상하좌우에 따라 비교해야할 위치와, 저장해야할 위치를 조금씩 바꿔서 나머지도 작성했다.

 

이러한 상하좌우로 드래그할 함수를 만든후 move()함수를 만들어 방향에 따라 함수를 호출하는 방식으로

각 단계마다 사방위를 탐색할 수 있도록 만들면 아래와 같다.

 

void dfs(int direct, int lv) {
    if(lv == 5) {   //마지막단계라면 큰수 찾아 리턴
        find_max();
        return;
    }
    
    memset(board[lv+1], 0, 20*20*sizeof(int));
    move(direct, lv);
    dfs(UP, lv+1);
    dfs(DOWN, lv+1);
    dfs(LEFT, lv+1);
    dfs(RIGHT, lv+1);
    //이전단계의 lv에서 상하좌우 이동을 다음단계 lv에 넘긴다.
}

void move(int direct, int lv) {
    switch (direct)
    {
    case UP:
        move_up(lv);
        break;
    case DOWN:
        move_down(lv);
        break;
    case LEFT:
        move_left(lv);
        break;
    case RIGHT:
        move_right(lv);
        break;
    default:
        break;
    }
}

 

여기서 내가 찾고자하는 최대 드래그 수인 5번째 드래그를 완료를 탈출조건으로 삼고 

탈출조건을 만족할시 해당 경우에서 최댓값을 찾아 갱신한다.

 

이러한 dfs를 다 돌고나면 모든 경우의 수를 탐색해(brute forcing) 최댓값을 찾을 수 있다.

 

https://github.com/shirohebiui/BAEKJOON/blob/55296720c00fd26f51e401f8cc10ab0d21b985cc/%23DFS/G/12100(G2)2048(easy).c