[삼성SW테스트] 백준 12100번 - 2048 (Easy) (정답률 23%)

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

12100번: 2048 (Easy)

삼성 SW테스트 기출문제다. (유형: 시뮬레이션 + DFS)

0번부터 최대 5번 판을 기울여 만들 수 있는 수 중 가장 큰 수를 구하는 문제다.

어차피 기울이면 이전과 같거나 더 큰 수가 나올 수 있기 때문에 5번 모두 기울인 경우를 고려해보면 된다.

 

다음 DFS로 넘어가고나서 바로 아래줄에 다음 회전경우를 위해 판을 재초기화 해주는 것이 중요하고,

회전 함수에서는 한 줄씩, 각 방향의 끝에서부터 큐에 0이 아닌 숫자를 담아준 뒤, 판의 해당 줄을 0으로 초기화해주고 인덱스 변수를 하나 잡아 순차적으로 조건에 맞게 넣어주면 되는 문제였다.

 

아래는 소스코드 (4ms)

#include <iostream>
#include <queue>
using namespace std;
const int MAX = 20;
int N;
int board[MAX][MAX];
int maxBlock;
void shift(int type)
{
    queue<int> q;
    //숫자들을 큐에 집어놓고 각 행의
    //해당방향 끝에서부터 숫자를 넣기 시작
    switch (type)
    {
        //왼쪽
    case 0:
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (board[i][j])
                    q.push(board[i][j]);
                board[i][j] = 0;
            }
            int idx = 0;
            while (!q.empty())
            {
                int data = q.front();
                q.pop();
                if (board[i][idx] == 0)
                    board[i][idx] = data;
                else if (board[i][idx] == data)
                {
                    board[i][idx] *= 2;
                    //시중에 나와있는 게임과 달리 여러번 합쳐지지 않는다
                    idx++;
                }
                else
                {
                    idx++;
                    board[i][idx] = data;
                }
            }
        }
        break;
        //오른쪽
    case 1:
        for (int i = 0; i < N; i++)
        {
            for (int j = N - 1; j >= 0; j--)
            {
                if (board[i][j])
                    q.push(board[i][j]);
                board[i][j] = 0;
            }
            int idx = N - 1;
            while (!q.empty())
            {
                int data = q.front();
                q.pop();
                if (board[i][idx] == 0)
                    board[i][idx] = data;
                else if (board[i][idx] == data)
                {
                    board[i][idx] *= 2;
                    idx--;
                }
                else
                {
                    idx--;
                    board[i][idx] = data;
                }
            }
        }
        break;
        //위쪽
    case 2:
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (board[j][i])
                    q.push(board[j][i]);
                board[j][i] = 0;
            }
            int idx = 0;
            while (!q.empty())
            {
                int data = q.front();
                q.pop();
                if (board[idx][i] == 0)
                    board[idx][i] = data;
                else if (board[idx][i] == data)
                {
                    board[idx][i] *= 2;
                    idx++;
                }
                else
                {
                    idx++;
                    board[idx][i] = data;
                }
            }
        }
        break;
        //아래쪽
    case 3:
        for (int i = 0; i < N; i++)
        {
            for (int j = N - 1; j >= 0; j--)
            {
                if (board[j][i])
                    q.push(board[j][i]);
                board[j][i] = 0;
            }
            int idx = N - 1;
            while (!q.empty())
            {
                int data = q.front();
                q.pop();
                if (board[idx][i] == 0)
                    board[idx][i] = data;
                else if (board[idx][i] == data)
                {
                    board[idx][i] *= 2;
                    idx--;
                }
                else
                {
                    idx--;
                    board[idx][i] = data;
                }
            }
        }
        break;
    }
}
void DFS(int cnt)
{
    if (cnt == 5)
    {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                maxBlock = max(maxBlock, board[i][j]);
        return;
    }
    int copyBoard[MAX][MAX];
    //현 보드상태 저장해놓고
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            copyBoard[i][j] = board[i][j];
    for (int i = 0; i < 4; i++)
    {
        shift(i);
        DFS(cnt + 1);
        //저장해놓은 보드상태로 원상복구
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                board[i][j] = copyBoard[i][j];
    }
}
int main(void)
{
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> board[i][j];
    DFS(0);
    cout << maxBlock << endl;
    return 0;
}