[백준] 삼성 SW 역량 테스트 기출 - 2048 (Easy) (C언어)

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

12100번: 2048 (Easy)

 

문제 해석

최대 20 * 20 의 2차원 공간에 상하좌우로 보드를 이동할 수 있고, 규칙에 따라 숫자가 이동 or 합산된다.

최초 입력되는 보드에서 최대 5번만 이동해 보드에서 가장 큰 블록의 값을 출력하는 문제이다.

1회 움직임에서 선택할 수 있는 경우는 상하좌우 4가지다. 최대 5번의 움직임만 생각하면 되므로 다해보면 되는 DFS 문제.

4 ^ 5 = 1024(움직임의 경우의 수)
=> 1024 * 20 * 20 = 409600 (움직임의 발생 횟수 * 보드의 크기)

 

상하좌우 4개의 함수를 구현해 따로 처리해도 되지만,
코딩 실수와 코딩 시간을 줄이기 위해서는 한가지 방향만 구현하고, 보드를 90도 돌리는 함수를 구현하면 코딩 시간을 줄일 수 있다.

#include <stdio.h>

int n;
int ret = 0;

struct BOARD
{
    int map[20][20];

    void rotate()
    {
        int temp[20][20];

        // 보드 90도 돌리기
        for (int y = 0; y < n; ++y)
        {
            for (int x = 0; x < n; ++x)
            {
                temp[y][x] = map[n - x - 1][y];
            }
        }
        // temp에 넣은 것 map에 복사
        for (int y = 0; y < n; ++y)
        {
            for (int x = 0; x < n; ++x)
            {
                map[y][x] = temp[y][x];
            }
        }
    }

    // 최대값 저장
    int get_max()
    {

        for (int y = 0; y < n; ++y)
        {
            for (int x = 0; x < n; ++x)
            {
                if (ret < map[y][x])
                {
                    ret = map[y][x];
                }
            }
        }
        return ret;
    }

    void up()
    {
        int temp[20][20];

        for (int x = 0; x < n; ++x)
        {
            // temp에 갱신이 있었는지 체크하는 플래그
            int flag = 0, target = -1;
            for (int y = 0; y < n; ++y)
            {
                if (map[y][x] == 0)
                {
                    continue;
                }
                // temp에 값이 한번 옮겨졌었고, 옮기려는 값과 앞에서 옮겨졌던 값(타겟팅된 값)이 같으면 업데이트
                if (flag == 1 && map[y][x] == temp[target][x])
                {
                    temp[target][x] *= 2, flag = 0;
                }
                else
                {
                    temp[++target][x] = map[y][x], flag = 1;
                }
            }
            // 값이 합쳐지고 나면 target이 끝까지 돌지 않고 끝나므로 돌면서 0으로 채워주기
            for (++target; target < n; ++target)
            {
                temp[target][x] = 0;
            }
        }
        // temp에 넣은 것 map에 복사
        for (int y = 0; y < n; ++y)
        {
            for (int x = 0; x < n; ++x)
            {
                map[y][x] = temp[y][x];
            }
        }
    }
};

void dfs(BOARD cur, int count)
{
    if (count == 5)
    {
        cur.get_max();
        return;
    }

    for (int dir = 0; dir < 4; ++dir)
    {
        BOARD next = cur;
        next.up();
        dfs(next, count + 1);
        cur.rotate();
    }
}

int main()
{
    BOARD board;
    scanf("%d", &n);
    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < n; ++x)
        {
            scanf("%d", &board.map[y][x]);
        }
    }

    ret = 0;
    dfs(board, 0);
    printf("%d\n", ret);

    return 0;
}