백준 12100번 2048 (Easy)

김두현·2023년 1월 5일

목록 보기

50/133

🔒[문제 url]

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

🔑알고리즘

기본적인 알고리즘은 다음과같다.
1. 상 : 0 하 : 1 좌 : 2 우 : 3 로 방향을 지정하고,
다섯번까지 이동시키므로 0 ~ 3으로 이루어진 길이가 5인 순열을 설정한다.BackTracking
2. 길이가 5인 모든 순열에 대해, 순열의 원소대로 블럭을 이동시킨다.
3. 다섯번씩 이동했을 때마다, 원소중 최대값끼리 비교하여 최대값을 출력한다. BruteForce

블럭을 어떻게 이동시키는가?

상하 방향으로 이동할때는 열 단위로,
좌우 방향으로 이동할때는 행 단위로 이동한다.
ex) 위로 이동 시, $i$ 번째 열의 모든 원소를 위로 옮긴 후 $i+1$ 번째 열을 옮긴다.

이동하고자 할때, 경우의 수는 다음과같이 세 가지이다.

다른 블럭과 합칠 수 있다.

합치지는 못하나, 이동할 수 있다.

합치지도, 이동하지도 못 한다.

즉, 한 블럭에 대해 1(우선순위) 2(후순위)를 3일때까지 반복한다. 이를 보드 내의 모든 블럭에 적용한다.

🐾부분 코드

int maxBlock()
{// 보드 내 가장 큰 블록 return
    int MAX = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            MAX = max(MAX, board[i][j]);
    return MAX;
}

<최대 크기 블럭 return 함수>
보드 내에서 가장 큰 블럭의 크기를 반환한다.

void copyBoard()
{// BackTracking을 위해 board 복사
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            board[i][j] = origin[i][j];
}

<보드 초기 상태 복사 함수>
각 순열마다 초기상태로부터 새로운 이동을 해야하므로, 원본을 저장해두고 이동할때마다 복사해준다.

void UP()
{

    for(int i = 0; i < n; i++)
    {// n개의 열에 대하여 위 원소부터 하나씩 올린다.

        for(int j = 1; j < n; j++)
        {
            // 이동할 원소의 현재 위치를 저장한다.
            int process = j;

            if (board[j][i] != 0)
            {
                while (true)
                {// 합칠수도, 옮길수도 없을때까지
                    
                    if (!gathered[process - 1][i]
                    && board[process][i] == board[process - 1][i])
                    {// 합쳐진다면
                        board[process - 1][i] += board[process][i];
                        board[process][i] = 0;
                        gathered[process - 1][i] = true;
                        break;
                    }
                    else if (board[process - 1][i] == 0 && 0 < process)
                    {// 옮길 수 있다면
                        board[process - 1][i] = board[process][i];
                        board[process][i] = 0;
                        process--;
                    }
                    else break;
                }
            }
        }// for j end
    }
}

<블럭을 위로 이동시키는 함수>
위로 이동하므로, 가장 윗 행의 원소부터 이동시킨다.
이동시킬 블럭은 행을 옮기게 되므로, 이동할때마다 process에 현재 row index를 저장한다.
합치거나 옮기지 못할때까지 1 2번을 수행한다.
나머지 방향도 알고리즘이 동일하므로, 따로 부분 코드를 작성하지 않았다. indexing 차이에만 유의하자.

🪄전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

int n;
int board[21][21], origin[21][21]; // 옮기는 보드, 원본
int permu[5];
bool gathered[21][21];

int ans = 0;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> origin[i][j];
}

int maxBlock()
{// 보드 내 가장 큰 블록 return
    int MAX = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            MAX = max(MAX, board[i][j]);
    return MAX;
}

void copyBoard()
{// BackTracking을 위해 board 복사
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            board[i][j] = origin[i][j];
}

void UP()
{

    for(int i = 0; i < n; i++)
    {// n개의 열에 대하여 위 원소부터 하나씩 올린다.

        for(int j = 1; j < n; j++)
        {
            // 이동할 원소의 현재 위치를 저장한다.
            int process = j;

            if (board[j][i] != 0)
            {
                while (true)
                {// 합칠수도, 옮길수도 없을때까지
                    
                    if (!gathered[process - 1][i]
                    && board[process][i] == board[process - 1][i])
                    {// 합쳐진다면
                        board[process - 1][i] += board[process][i];
                        board[process][i] = 0;
                        gathered[process - 1][i] = true;
                        break;
                    }
                    else if (board[process - 1][i] == 0 && 0 < process)
                    {// 옮길 수 있다면
                        board[process - 1][i] = board[process][i];
                        board[process][i] = 0;
                        process--;
                    }
                    else break;
                }
            }
        }// for j end
    }
}

void DOWN()
{
    for(int i = 0; i < n; i++)
    {// n개의 열에 대하여 아래 원소부터 하나씩 내린다.

        for(int j = n - 2; j >= 0; j--)
        {
            int process = j;

            if (board[j][i] != 0)
            {
                while (true)
                {
                    if (!gathered[process + 1][i]
                    && board[process][i] == board[process + 1][i])
                    {// 합쳐진다면
                        board[process + 1][i] += board[process][i];
                        board[process][i] = 0;
                        gathered[process + 1][i] = true;
                        break;
                    }
                    else if (board[process + 1][i] == 0 && process < n - 1)
                    {// 옮길 수 있다면
                        board[process + 1][i] = board[process][i];
                        board[process][i] = 0;
                        process++;
                    }
                    else break;
                }
            }
        }// for j end
    }

}

void LEFT()
{
    for(int i = 0; i < n; i++)
    {// n개의 행에 대하여 왼쪽 원소부터 하나씩 왼쪽으로 민다.

        for(int j = 1; j < n; j++)
        {
            int process = j;

            if (board[i][j] != 0)
            {
                while (true)
                {
                    if (!gathered[i][process - 1]
                    && board[i][process - 1] == board[i][process])
                    {// 합쳐진다면
                        board[i][process - 1] += board[i][process];
                        board[i][process] = 0;
                        gathered[i][process - 1] = true;
                        break;
                    }
                    else if (board[i][process - 1] == 0 && 0 < process)
                    {// 옮길 수 있다면
                        board[i][process - 1] = board[i][process];
                        board[i][process] = 0;
                        process--;
                    }
                    else break;
                }
            }
        }// for j end
    }

}

void RIGHT()
{

    for(int i = 0; i < n; i++)
    {// n개의 행에 대하여 왼쪽 원소부터 하나씩 오른쪽으로 민다.

        for(int j = n - 2; j >= 0; j--)
        {
            int process = j;

            if (board[i][j] != 0)
            {
                while (true)
                {
                    if (!gathered[i][process + 1]
                    && board[i][process + 1] == board[i][process])
                    {// 합쳐진다면
                        board[i][process + 1] += board[i][process];
                        board[i][process] = 0;
                        gathered[i][process + 1] = true;
                        break;
                    }
                    else if (board[i][process + 1] == 0 && process < n - 1)
                    {// 옮길 수 있다면
                        board[i][process + 1] = board[i][process];
                        board[i][process] = 0;
                        process++;
                    }
                    else break;
                }
            }
        }// for j end
    }
}

void move()
{// 이동 방향 순열이 정해졌다면, 순열대로 이동
    for(int i = 0; i < 5; i++)
    {
        int dir = permu[i];

        for(int k = 0; k < n; k++)
            for(int j = 0; j < n; j++)
                gathered[k][j] = false;
        if(dir == 0) UP();
        else if(dir == 1) DOWN();
        else if(dir == 2) LEFT();
        else RIGHT();
    }

    ans = max(ans, maxBlock());
}

void setPermu(int cnt)
{// 이동 방향 순열 설정
    if(cnt == 5)
    {
        copyBoard();
        move();
        return;
    }

    for(int i = 0; i < 4; i++)
    {
        permu[cnt] = i;
        setPermu(cnt + 1);
    }
}
void SOLVE()
{
    setPermu(0);
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}