백준 12100번 2048(Easy) [C++]

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

12100번: 2048 (Easy)

 

 

#문제 간단 정리

기존의 https://dfdfg42.tistory.com/manage/newpost/55?type=post&returnURL=https%3A%2F%2Fdfdfg42.tistory.com%2Fmanage%2Fposts

https://dfdfg42.tistory.com/manage/newpost/55?returnURL=https%3A%2F%2Fdfdfg42.tistory.com%2Fmanage%2Fposts&type=post

감시 문제에서 좀 더 귀찮아진 문제라고 볼 수 있다.

구현 +시뮬레이션 + 백트래킹

 

#문제 해결 방법

기존 감시 문제와 비슷하게 구현하지만 여기서 생각해야 될점이

상 하 좌 우로 합쳐질때 

테이블을 순회하는 순서가 각각 달라야 된다는 것이다

우선 감시문제와 같게

dfs 코드

그리고 가장 높은 블럭을 조사하는 함수

그리고 이동을 담당하는 함수 파트로

나뉘어서 구현해야된다고 생각할 수 있는데

여기서 이동할 때 맵을 순회하는게 상 하 좌 우 에 따라서 

다르게 조회해야된다는것이다.

 

위쪽으로 합칠때는 0,0 부터 20,20 까지 순서대로 조회하면 되지만

좌측으로 합칠 때는 좌측 열부터 조회해야되기때문에 0,0에서 0,20 그리고 20,20으로 조회해야 된다는 것이다

이를 신경쓰는게 주 문제였다.

 

#전체 코드

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

int N;
int board[20][20];

// 상하좌우 이동에 대한 인덱스
const int dx[4] = {-1, 1, 0, 0}; // 상, 하
const int dy[4] = {0, 0, -1, 1}; // 좌, 우

// 보드 상태를 복사하는 함수
void copyBoard(int src[20][20], int dest[20][20]) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dest[i][j] = src[i][j];
        }
    }
}

// 블록 이동 및 합치기 로직
void moveAndMerge(int direction) {
    bool merged[20][20] = {false}; // 합쳐진 블록을 표시하기 위한 배열
    if (direction == 0 || direction == 2) { // 상, 좌 방향
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (board[i][j] == 0) continue;
                int x = i + dx[direction];
                int y = j + dy[direction];
                while (x >= 0 && x < N && y >= 0 && y < N) {
                    if (board[x][y] == 0) { // 빈 칸으로 이동
                        board[x][y] = board[x - dx[direction]][y - dy[direction]];
                        board[x - dx[direction]][y - dy[direction]] = 0;
                        x += dx[direction];
                        y += dy[direction];
                    } else if (board[x][y] == board[x - dx[direction]][y - dy[direction]] && !merged[x][y]) {
                        // 같은 값의 블록과 합치기
                        board[x][y] *= 2;
                        board[x - dx[direction]][y - dy[direction]] = 0;
                        merged[x][y] = true;
                        break;
                    } else {
                        break;
                    }
                }
            }
        }
    } else { // 하, 우 방향
        for (int i = N - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                if (board[i][j] == 0) continue;
                int x = i + dx[direction];
                int y = j + dy[direction];
                while (x >= 0 && x < N && y >= 0 && y < N) {
                    if (board[x][y] == 0) {
                        board[x][y] = board[x - dx[direction]][y - dy[direction]];
                        board[x - dx[direction]][y - dy[direction]] = 0;
                        x += dx[direction];
                        y += dy[direction];
                    } else if (board[x][y] == board[x - dx[direction]][y - dy[direction]] && !merged[x][y]) {
                        board[x][y] *= 2;
                        board[x - dx[direction]][y - dy[direction]] = 0;
                        merged[x][y] = true;
                        break;
                    } else {
                        break;
                    }
                }
            }
        }
    }
}

int findMaxBlock() {
    int maxBlock = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            maxBlock = max(maxBlock, board[i][j]);
        }
    }
    return maxBlock;
}

int dfs(int depth) {
    if (depth == 5) { // 최대 이동 횟수에 도달
        return findMaxBlock();
    }

    int maxBlock = 0, backup[20][20];
    for (int direction = 0; direction < 4; ++direction) {
        copyBoard(board, backup); // 현재 상태 백업
        moveAndMerge(direction); // 이동 및 합치기
        maxBlock = max(maxBlock, dfs(depth + 1)); // 재귀적으로 최대 블록 값 찾기
        copyBoard(backup, board); // 백업에서 원래 상태로 복원
    }
    return maxBlock;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> board[i][j];
        }
    }

    cout << dfs(0) << endl;
    return 0;
}