[BOJ] C++ 12100: 2048(Easy) - 감시와 유사한 완전 탐색 구현

[BOJ] C++ 12100: 2048(Easy) - 감시와 유사한 완전 탐색 구현

2023. 11. 26. 15:56ㆍ알고리즘/문제풀이

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

2048 게임을 5번 진행했을 때 얻을 수 있는 최대 수를 구하면 되는 문제이다. 백트래킹이나 다른 특별한 풀이가 안 떠올라서 먼저 완전탐색으로 가능한지 계산해 보았다.

20*20 크기의 보드에 한 번 이동당 최대 4개의 경우의 수가 있으므로 총 1024개의 보드를 탐색하면 된다. 1024개에 대해 보드를 이동시키는데 N^2 만큼의 시간이 든다고 가정하면 총 시간복잡도는 1024 * N^2 * 5이므로 무조건 가능하다고 생각하고 완전탐색으로 풀이 방향을 잡았다.

알고리즘의 구현 사항은 크게 두 가지로 나뉜다.

판을 4 방향으로 이동시키기
모든 경우의 수 완전 탐색
모든 경우의 수를 탐색하는 부분은 전에 감시 문제로 푼 적 있으므로 똑같이 재귀로 구현하면 쉽게 해결 가능하다. 잘 모르겠다면 아래 문제를 풀어보자!

[BOJ] C++ 15683: 감시 - 백트래킹과 재귀, 시뮬레이션의 전형적인 문제

2023.10.25 - [알고리즘/문제풀이] - [BOJ] C++ 15655 N과 M (6) - 제한이 까다로운 백트래킹 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼

jun-n.tistory.com

판을 4방향으로 이동시키는 걸 구현하는 게 가장 핵심인데, 이동시킬 때 각 행/열 별로 독립적으로 이동한다. 예를 들어 위쪽으로 이동시키려면 각 열별로 독립적으로 이동되므로 그거만 구현해 주면 된다. 이런저런 방법이 떠올랐지만 가장 쉽고 강력한 해법은 새 배열을 만들어서 실제로 이동시키는 방법이다. 삽입정렬 어디쯤에서 본 것 같은 느낌으로 새 배열에 현재까지 삽입한 index를 기억해두고 그 index에 값이 없다면 그냥 삽입, 값이 있는데 현재 삽입하려는 값과 똑같다면 *2를 해주면서 index++, 값이 다르다면 그 다음칸에 삽입하는 방식이다. 이런 방법이 아니라 다른 방법이라도 엔간하면 시간 안에 풀 수 있을 것이다.

void moving_upward()
{
    // 각 열을 위로 이동시키면서 풀어보자.
    int res_board[22][22];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res_board[i][j] = 0;

    for (int col = 0; col < n; col++)
    {
        int cur = 0;
        // col열을 위로 이동시키면 된다.
        for (int i = 0; i < n; i++)
        {
            if (board[i][col] == 0)
                continue;
            if (res_board[cur][col] == 0)
            {
                res_board[cur][col] = board[i][col];
            }
            else if (res_board[cur][col] == board[i][col])
            {
                res_board[cur++][col] *= 2;
            }
            else
            {
                res_board[++cur][col] = board[i][col];
            }
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = res_board[i][j];
}

다른 방향도 똑같이 구현해주면 판을 4방향으로 이동시키는 부분은 구현 끝이다. 이제 모든 경우의 수를 정말탐색해 주면 되는데, 재귀로 풀었다.

함수 정의
void func(int k) : 현재 판을 k번 이동시킴
base condition
if(k == 5) 가장 큰 블록 계산 후 종료
재귀식
특정 방향으로 이동시킨 후 func(k+1) 호출, 호출이 끝나면 다시 보드 복구

실제로 문제를 풀 때도 위의 방식과 똑같이 먼저 구성해 놓고 그대로 구현했다. 재귀에 겁먹지 말고 딱 저 세 요소만 미리 구성해 두면 오히려 구현하기 더 쉽다.

void func(int k)
{
    if (k == 5)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                max_ = max(max_, board[i][j]);
        return;
    }
    // 현재 k번만큼 블럭을 이동시킴.

    // 특정 방향으로 이동시키고 func(k+1)호출, 호출이 끝나면 다시 원상복구 시키기
    int tmp_board[22][22];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            tmp_board[i][j] = board[i][j];

    // 위쪽 방향으로 이동
    moving_upward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];

    // 아래 방향으로 이동
    moving_downward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];

    // 왼쪽 방향으로 이동
    moving_leftward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];
    // 오른쪽 방향으로 이동
    moving_rightward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];
}

풀 코드

/** 시뮬레이션 12100 2048(Easy) **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n;
int board[22][22];
int max_ = 0;

void moving_upward()
{
    // 각 열을 위로 이동시키면서 풀어보자.
    int res_board[22][22];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res_board[i][j] = 0;

    for (int col = 0; col < n; col++)
    {
        int cur = 0;
        // col열을 위로 이동시키면 된다.
        for (int i = 0; i < n; i++)
        {
            if (board[i][col] == 0)
                continue;
            if (res_board[cur][col] == 0)
            {
                res_board[cur][col] = board[i][col];
            }
            else if (res_board[cur][col] == board[i][col])
            {
                res_board[cur++][col] *= 2;
            }
            else
            {
                res_board[++cur][col] = board[i][col];
            }
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = res_board[i][j];
}

void moving_downward()
{
    // 각 열을 아래로 이동시키면서 풀어보자.
    int res_board[22][22];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res_board[i][j] = 0;

    for (int col = 0; col < n; col++)
    {
        int cur = n - 1;
        // col열을 아래로 이동시키면 된다.
        for (int i = n - 1; i >= 0; i--)
        {
            if (board[i][col] == 0)
                continue;
            if (res_board[cur][col] == 0)
            {
                res_board[cur][col] = board[i][col];
            }
            else if (res_board[cur][col] == board[i][col])
            {
                res_board[cur--][col] *= 2;
            }
            else
            {
                res_board[--cur][col] = board[i][col];
            }
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = res_board[i][j];
}

void moving_leftward()
{
    // 각 행을 왼쪽으로 이동시키면서 풀어보자.
    int res_board[22][22];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res_board[i][j] = 0;

    for (int row = 0; row < n; row++)
    {
        int cur = 0;
        // row행을 왼쪽으로 이동시키면 된다.
        for (int i = 0; i < n; i++)
        {
            if (board[row][i] == 0)
                continue;
            if (res_board[row][cur] == 0)
            {
                res_board[row][cur] = board[row][i];
            }
            else if (res_board[row][cur] == board[row][i])
            {
                res_board[row][cur++] *= 2;
            }
            else
            {
                res_board[row][++cur] = board[row][i];
            }
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = res_board[i][j];
}

void moving_rightward()
{
    // 각 행을 오른쪽으로 이동시키면서 풀어보자.
    int res_board[22][22];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res_board[i][j] = 0;

    for (int row = 0; row < n; row++)
    {
        int cur = n - 1;
        // row행을 오른쪽으로 이동시키면 된다.
        for (int i = n - 1; i >= 0; i--)
        {
            if (board[row][i] == 0)
                continue;
            if (res_board[row][cur] == 0)
            {
                res_board[row][cur] = board[row][i];
            }
            else if (res_board[row][cur] == board[row][i])
            {
                res_board[row][cur--] *= 2;
            }
            else
            {
                res_board[row][--cur] = board[row][i];
            }
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = res_board[i][j];
}

void func(int k)
{
    if (k == 5)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                max_ = max(max_, board[i][j]);
        return;
    }
    // 현재 k번만큼 블럭을 이동시킴.

    // 특정 방향으로 이동시키고 func(k+1)호출, 호출이 끝나면 다시 원상복구 시키기
    int tmp_board[22][22];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            tmp_board[i][j] = board[i][j];

    // 위쪽 방향으로 이동
    moving_upward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];

    // 아래 방향으로 이동
    moving_downward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];

    // 왼쪽 방향으로 이동
    moving_leftward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];
    // 오른쪽 방향으로 이동
    moving_rightward();
    func(k + 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            board[i][j] = tmp_board[i][j];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> board[i][j];

    func(0);
    cout << max_ << '\n';
}

저작자표시 비영리 변경금지

'알고리즘 > 문제풀이' 카테고리의 다른 글

[BOJ] C++ 11559: Puyo Puyo - BFS로 구현한 시뮬레이션 (2)	2023.11.27
[BOJ] C++ 15686: 치킨 배달 - 조합(combination) 계산하여 완전 탐색 (1)	2023.11.26
[BOJ] C++ 18808: 스티커 붙이기 - 시뮬레이션 (1)	2023.11.23
[문제풀이] 2차원 배열 90도 회전, 뒤집기 꿀팁 (0)	2023.11.23
[BOJ] C++ 15683: 감시 - 백트래킹과 재귀, 시뮬레이션의 전형적인 문제 (3)	2023.11.21

조준화의 오류정정

조준화의 오류정정

태그

최근글

댓글

공지사항

아카이브

'알고리즘 > 문제풀이' 카테고리의 다른 글

관련글

티스토리툴바