BOJ 12100 · 2048 (Easy)

알고리즘 분류 : 브루트 포스, 시뮬레이션  

게임 '2048'을 구현하는 문제다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 구해야 한다.

• 2048을 구현하기 위해 크게 두 단계로 나눈다.
• 첫 번째, 숫자 블록을 움직이는 단계, 두 번째, 블록을 합치는 단계이다.
• 1. 움직이는 단계는 상, 하, 좌, 우 방향으로 총 4가지의 경우의 수가 있다.
• 움직일 때, 방향에 따라 해당 열(또는 행)의 숫자 블록을 큐에 넣는다. 빈 공간(0)은 넣지 않는다. 블록을 넣었다면, 블록에 있던 자리는 빈 공간(0)으로 만든다.
• 2. 합치는 단계에서는 큐에서 블록을 꺼내고 이를 순서대로 보드와 비교하면서 진행한다.
• 만약 현재 좌표 보드가 빈 공간(0)이라면, 큐에 꺼낸 숫자를 그대로 보드에 놓는다.
• 보드에 현재 좌표에 숫자가 이미 놓여있다면, 큐에서 꺼낸 블록과 값이 일치하는지 비교한다.
• 같으면 현재 좌표의 보드 숫자를 2배로 하고, 다르면 다음 좌표에 꺼낸 숫자를 둔다.
• 1, 2 과정을 반복한다.
• 방향을 바꿀 때마다 원래 보드를 써야 하므로, 별도의 배열을 만들어 보드를 저장할 필요가 있다. C++의 경우 memcpy를 쓰면 유용하다.

---

C++ 소스코드

#include <queue>
using namespace std;

int n, ans;
int a[20][20];
queue<int> q;

void get(int i, int j) {
    if (a[i][j]) {
        q.push(a[i][j]);
        a[i][j] = 0;
    }
}

void merge(int i, int j, int di, int dj) {
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (!a[i][j]) a[i][j] = x;
        else if (a[i][j] == x) {
            a[i][j] = x*2;
            i += di, j += dj;
        }
        else {
            i += di, j += dj;
            a[i][j] = x;
        }
    }   
}

void move(int k) {
    if (k == 0) {
        // Up
        for (int j=0; j<n; j++) {
            for (int i=0; i<n; i++) get(i, j);
            merge(0, j, 1, 0);
        }
    } else if (k == 1) {
        // Down
        for (int j=0; j<n; j++) {
            for (int i=n-1; i>=0; i--) get(i, j);
            merge(n-1, j, -1, 0);
        }
    } else if (k == 2) {
        // Left
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) get(i, j);
            merge(i, 0, 0, 1);
        }
    } else {
        // Right
        for (int i=0; i<n; i++) {
            for (int j=n-1; j>=0; j--) get(i, j);
            merge(i, n-1, 0, -1);
        }
    }
}

void solve(int cnt) {
    if (cnt == 5) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (ans < a[i][j]) ans = a[i][j];
            }
        }
        return;
    }
    int b[20][20];
    memcpy(b, a, sizeof(a));
    for (int k=0; k<4; k++) {
        move(k);
        solve(cnt+1);
        memcpy(a, b, sizeof(b));
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    solve(0);
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

from collections import deque
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans, q = 0, deque()

def get(i, j):
    if a[i][j]:
        q.append(a[i][j])
        a[i][j] = 0

def merge(i, j, di, dj):
    while q:
        x = q.popleft()
        if not a[i][j]:
            a[i][j] = x
        elif a[i][j] == x:
            a[i][j] = x*2
            i, j = i+di, j+dj
        else:
            i, j = i+di, j+dj
            a[i][j] = x

def move(k):
    if k == 0:
        for j in range(n):
            for i in range(n):
                get(i, j)
            merge(0, j, 1, 0)
    elif k == 1:
        for j in range(n):
            for i in range(n-1, -1, -1):
                get(i, j)
            merge(n-1, j, -1, 0)
    elif k == 2:
        for i in range(n):
            for j in range(n):
                get(i, j)
            merge(i, 0, 0, 1)
    else:
        for i in range(n):
            for j in range(n-1, -1, -1):
                get(i, j)
            merge(i, n-1, 0, -1)

def solve(cnt):
    global a, ans
    if cnt == 5:
        for i in range(n):
            ans = max(ans, max(a[i]))
        return
    b = [x[:] for x in a]
    for k in range(4):
        move(k)
        solve(cnt+1)
        a = [x[:] for x in b]

solve(0)
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 12100