c++) 백준 12100-2048(easy)

문제 : 12100번: 2048 (Easy) (acmicpc.net)

12100번: 2048 (Easy)

주의할 점

1. 모든 경우의 수를 탐색해야하는 완전탐색 문제입니다.

2. 재귀호출 시 다음 상태로 넘어가기 전에 백업 -> 호출 -> 복원 해주는 과정이 필요합니다.

3. 백업을 위한 배열을 각 함수가 실행될 때마다 선언해줘야 합니다.

아래에서 설명하겠습니다.

 

풀이과정 1

1. solution() 함수를 통해 상하좌우 4가지 경우를 전부 탐색합니다.

(기저사례) : 만약 5번 이동시켰을 경우 최대값을 비교해서 저장합니다.

 

2. solution() 함수가 실행 될 때마다 이동하기기 전 상태를 저장하기 위해 temp 배열을 각각 선언하고

저장해줍니다.

 

왜 백업을 위한 temp 배열을 재귀호출 시마다 선언해야할까?

※ 만약 temp 배열을 전역배열로 바깥에 선언했을 경우를 생각해봅시다.

이 경우 재귀호출을 통해 2 depth 만큼 들어간다고 한다면,

(각각 depth1, depth2 에서의 board 상태를 board1, board2 라고 하겠습니다.) 

 

1. depth1 에서 해당 board1 값이 저장되고

2. depth2 에서 해당 board2 값이 저장됩니다.

3. 그리고 depth2에서 빠져나올 때 복원하면 board2에 해당하는 값이 저장됩니다.

4. 그리고나서  depth1에서 빠져나올 때 복원하면 이미 temp배열 에는 board2에 해당하는 값이

마지막에 저장되어있기 때문에 board1 값이 아닌 board2 값이 복원됩니다.

 

그러나 temp 지역배열을 호출할 때마다 선언해 준다면 위와 같은 문제가 발생하지 않고

해당 depth의 값이 따로따로 저장됩니다.

 

풀이과정 2

3. moveAndMerge 함수를 통해 실제 board를 움직입니다.

상하좌우 4방향을 고려해야합니다.

 

4. 재귀호출을 통해 다음 depth로 이동하고, 끝났을 때 앞서 저장했던 값을 복원합니다.

코드

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <deque>
#include <algorithm>
using namespace std;
int N,ans = -1;

void moveAndMerge(vector < vector < int > > &board, int dir) {
    // 위
    deque < int > dq;
    if(dir == 0) {
        for(int x=0; x<N; x++) {
            for(int y=0; y<N; y++) {
                if(board[y][x]) dq.push_back(board[y][x]);
                board[y][x] = 0;
            }
            int idx = 0;
            while(!dq.empty()) {
                int num = dq.front();
                dq.pop_front();

                if(board[idx][x] == 0)
                    board[idx][x] = num;
                else if(board[idx][x] == num) {
                    board[idx][x] *= 2;
                    idx++;
                }
                else {
                    idx++;
                    board[idx][x] = num;
                }
            }
        }
    }
    // 아래
    if(dir == 1) {
        for(int x=0; x<N; x++) {
            for(int y=N-1; y>=0; y--) {
                if(board[y][x]) dq.push_back(board[y][x]);
                board[y][x] = 0;
            }

            int idx = N-1;
            while(!dq.empty()) {
                int num = dq.front();
                dq.pop_front();

                if(board[idx][x] == 0)
                    board[idx][x] = num;
                else if(board[idx][x] == num) {
                    board[idx][x] *= 2;
                    idx--;
                }
                else {
                    idx--;
                    board[idx][x] = num;
                }
            }
        }
    }
    // 왼쪽
    if(dir == 2) {
        for(int y=0; y<N; y++) {
            for(int x=0; x<N; x++) {
                if(board[y][x]) dq.push_back(board[y][x]);
                board[y][x] = 0;
            }
            int idx = 0;
            while(!dq.empty()) {
                int num = dq.front();
                dq.pop_front();

                if(board[y][idx] == 0)
                    board[y][idx] = num;
                else if(board[y][idx] == num) {
                    board[y][idx] *= 2;
                    idx++;
                }
                else {
                    idx++;
                    board[y][idx] = num;
                }
            }
        }
    }
    // 오른쪽
    if(dir == 3) {
        for(int y=0; y<N; y++) {
            for(int x=N-1; x >= 0; x--) {
                if(board[y][x]) dq.push_back(board[y][x]);
                board[y][x] = 0;
            }

            int idx = N-1;
            while(!dq.empty()) {
                int num = dq.front();
                dq.pop_front();

                if(board[y][idx] == 0)
                    board[y][idx] = num;
                else if(board[y][idx] == num) {
                    board[y][idx] *= 2;
                    idx--;
                }
                else {
                    idx--;
                    board[y][idx] = num;
                }
            }
        }
    }
}

void solution(vector < vector < int > > &board, int cnt) {
    // 기저사례 : 5번 이동했을 경우 최대값을 비교한다
    if(cnt == 5) {
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                ans = max(ans,board[i][j]);
        return;
    }

    // 백업
    int temp[N][N];
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            temp[i][j] = board[i][j];

    // 모든 경우의 수 탐색
    for(int dir=0; dir<4; dir++) {
        moveAndMerge(board,dir);
        solution(board,cnt+1);
        // 복원
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                board[i][j] = temp[i][j];
    }
}



int main()
{
    scanf("%d",&N);
    vector < vector < int > >board(N, vector<int>(N,0));
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            scanf("%d",&board[i][j]);
        }
    }
    solution(board,0);
    printf("%d\n",ans);
}