백준) 12100 2048 (Easy)

2048 (Easy)

2048 게임을 하는데 5번 이동에 제일 큰 블록을 만들어야 한다.

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

블록이 어떻게 주어질지 모르니까 전략이 없다. 모든 경우를 실험해보자.

같은 상태에 도달하면 다시 할 필요가 없긴 하지만, 같은 상태를 확인하기도, 도달하기도 어렵다.

걍 백트래킹으로 조져보자.

백트래킹 함수는 다음과 같이 구성했다.

상단엔 5번 이동했는지 확인한다. 5번이면 가장 큰 블록을 찾아 답과 비교하고 종료시킨다.

5번 이하의 경우에 완전탐색을 수행해야 하는데,

이전 상태를 저장 -> 재귀호출 -> 복귀 와 같은 아주 간단한 구조로 되어있다.

아래 코드는 매우 더러우니 안 보는 것을 추천합니다..

4방향의 규칙을 다 하드코딩으로 해놓았기 때문에 가독성이 구리다.

포문으로 임시변수 가로줄에 옮기고, 합치고, 되돌려주면 되긴 하는데 시간에 쫓겨 그냥 다 해버렸다 ^오^

아이디어만 얻어가시면 되는데,

한 줄씩 블록을 합치는 것과, 진짜 블록만 스택에 넣고 다시 줄을 채우는 것으로 병합을 구현했다.

#include <stdio.h>
#include <stack>
using namespace std;
 
int n, ans;
int map[20][20];
 
void save(int tmap[][20]) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            tmap[i][j] = map[i][j];
}
 
void restore(int tmap[][20]) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            map[i][j] = tmap[i][j];
}
 
void backtracking(int cnt) {
    if (cnt == 5) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (ans < map[i][j])
                    ans = map[i][j];
 
        return;
    }
 
    stack<int> st;
    int tmap[20][20];
    save(tmap);
 
    for (int i = 0; i < n; ++i) { //우
        for (int j = 0; j < n; ++j) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = n - 1;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[i][b])
                map[i][b] = t;
            else if (t == map[i][b])
                map[i][b--] *= 2;
            else
                map[i][--b] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int i = 0; i < n; ++i) { //좌
        for (int j = n - 1; j >= 0; --j) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = 0;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[i][b])
                map[i][b] = t;
            else if (t == map[i][b])
                map[i][b++] *= 2;
            else
                map[i][++b] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int j = 0; j < n; ++j) { //위
        for (int i = 0; i < n; ++i) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = n - 1;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[b][j])
                map[b][j] = t;
            else if (t == map[b][j])
                map[b--][j] *= 2;
            else
                map[--b][j] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int j = 0; j < n; ++j) { //아래
        for (int i = n - 1; i >= 0; --i) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = 0;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[b][j])
                map[b][j] = t;
            else if (t == map[b][j])
                map[b++][j] *= 2;
            else
                map[++b][j] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &map[i][j]);
 
    backtracking(0);
    printf("%d", ans);
 
    return 0;
}