[삼성 기출 문제] 백준 12100 2048 (easy)

문제 링크

클릭시 문제로 이동합니다.

어떻게 풀까?

해당 문제는 크게 2 부분으로 나눌 수 있습니다.

1. 재귀를 이용하여 블록을 위/아래/왼쪽/오른쪽 으로 최대 5번 이동시키는 부분

2. 이동시켜서 최댓값이 어떻게 되는지 알아내는 부분

이 중, 1번은 2차원 배열 restore[][]를 이용하면, 기존의 맵을 저장하고 복구하면서 맵을 5번까지 이동시키는 방법으로 구현할 수 있습니다.

가장 중요한건 2번이죠!

switch를 쓰면 비슷한 방법을 4번 반복해야하기 때문에, 짧게 이를 해결하는 방법을 소개해드리겠습니다.

(물론, 실전에서 이 방법까지 생각하려면 힘들겠지만, 그래도! 여긴 블로그니까요!)

우선, 기본적으로 블록을 이동시키는 방법은 덱을 이용하는 것입니다.

덱의 맨 뒤의 수와, 현재 맵에 적혀있는 블록들을 확인하면서, 두 수가 같으면 더해주는 것이죠!

또한, 더해진 수에 또 한번 더해지면 안되기 때문에 canplus라는 변수를 사용합시다!

canplus가 true면, 현재 덱의 맨 뒤의 수가 더해질 수 있다는 것을 의미하고, false인 경우에는 더해질 수 없다는 것을 의미합니다!

예를 들어, 1, 1, 2, 4블럭을 왼쪽으로 이동시켜 보겠습니다.

1을 큐에 넣습니다! 다음에 1이 들어오면 두 수가 더해질 수 있기 때문에 canplus는 true 입니다.

그리고, 초록색 부분을 0으로 채웁니다.

canplus가 true이고 덱의 맨 뒤가 1이기 때문에 두 수를 합칩니다.

그리고, 합쳐졌으니 canplus는 false로 만들고, 초록색 부분은 0으로 만듭니다.

같은 2가 들어왔지만, 합쳐지지 않습니다.

초록색 부분을 0으로 만듭니다.

canplus가 false이므로 덱의 맨 뒤에는 4를 넣습니다.

그리고 이제 맵의 끝에 닿았기 때문에, 덱의 앞에서부터 다시 맵을 채워넣으면,

이렇게 완성됩니다!

하지만, 왼쪽, 오른쪽, 위, 아래로 블럭이 이동할때마다 기준점이 달라집니다. 어떻게 하면 이 기준점을 쉽게 만들 수 있을까요!?

자! 우선 규칙을 정합시다.

d는 블럭들이 이동해야하는 방향을 의미합니다.

d[0] = 왼쪽

d[1] = 오른쪽

d[2] = 위

d[3] = 아래

자, 블럭들이 왼쪽으로 이동해야 하는 경우입니다.

이 경우에, 블록을 이동시키기 위해서는 어떤 행을 기준으로 가장 왼쪽부터 이동해야합니다.

아래 그림에서 초록색으로 칠한 부분들과 같죠.

이와 유사하게, 오른쪽, 위, 아래로 이동해야하는 경우는 아래 그림들과 같습니다.

즉, 4 개의 처음 확인해야하는 지점이 모두 다른 것을 알 수 있습니다.

하지만, 왼쪽과 오른쪽, 위와 아래로 묶으면 약간의 공통점이 있습니다.

왼쪽과 오른쪽은 0행부터 n행까지 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 본다는 것입니다. 즉, 왼쪽으로 이동할때는 다음의 맵이 arr[0][1]로 1 증가하고, 오른쪽으로 이동해야할 때는 덱에 넣어야할 다음 맵의 위치가 arr[0][n-2]가 됩니다.

시작점 : arr[0][0], arr[0][n-1]

다음 지점 : 열 +1, 열 -1

위와 아래는 이와 반대입니다.

시작점 : arr[0][0], arr[n-1][0]

다음 지점 : 행 +1, 행 -1

이를 이용해서 다음 지점으로 이동해야하는 dm[4] 를 {1,-1,1,-1}로 하고,

시작지점을 start[4] = {0,1,0,1}로 해서

처음 시작지점을 a, b 변수로 두고,

a를 0, b를 start[d] * (n-1)로 한 뒤에,

상하를 보는지, 위 아래를 보는지에 따라서 arr[a][b]를 할지 arr[b][a]를 볼지 정해주면 됩니다.

그리고, b값에 dm[d]를 더해주면 되죠!

만약, b가 0이 되거나 n이 된다면, a를 1 늘려서 위의 과정을 다시 반복하면 됩니다.

마지막으로, 맵을 훑어 보면서 최댓값이 무엇인지 찾으면 되죠!

코드

//https://www.acmicpc.net/problem/12100
// BOJ 12100 2048(easy)
#pragma once
#include<iostream>
#include<cstring>
 
using namespace std;
 
int map[20][20], n;
int dm[4] = { 1,-1,1,-1 };
int start[4] = { 0,1,0,1 };
int MAX(int i1, int i2) { return i1 < i2 ? i2 : i1; }
 
void move(int d) {
    int que[20], s = 0, e = 0;
 
    for (int j = 0; j < n; j++) {
        s = e = 0;
        bool canpl = false;
        int r = start[d] * (n - 1);
        while (r >= 0 && r < n) {
            int &nblock = d & 2 ? map[j][r] : map[r][j];
            if (nblock) {
                if (canpl && que[e - 1] == nblock) {
                    canpl = false;
                    que[e - 1] <<= 1;
                    nblock = 0;
                }
 
                else {
                    canpl = true;
                    que[e++] = nblock;
                    nblock = 0;
                }
            }
            r += dm[d];
        }
 
        r = start[d] * (n - 1);
 
        while (s != e) {
            int &nblock = d & 2 ? map[j][r] : map[r][j];
            nblock = que[s++];
            r += dm[d];
        }
    }
}
 
int dfs(int depth, int dir) {
    if (depth == 5) {
        int max = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) max = MAX(map[i][j], max);
 
        return max;
    }
 
    int restore[20][20];
 
    memcpy(restore, map, sizeof(map));
 
    int num = 0;
 
    for (int i = 0; i < 4; i++) {
        move(i);
        num = MAX(num, dfs(depth + 1, i));
        memcpy(map, restore, sizeof(map));
    }
 
    return num;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    cout << dfs(0, 0);
    return 0;
}

시간 복잡도

총 시간복잡도는 입니다.

물론, 재귀함수가 4개의 노드씩 5번 생성되기 때문에 번 돌아갑니다!