(C++) [백준 12100번] 2048(Easy)

+) 글 작성에 앞서!

내가 짠 코드보다 훨씬 간결하고 효율적인 코드가 있다.

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/12100.cpp

바킹독님 코드인데, 직접 4방향으로 돌려보지 않고 배열을 회전시키는 방법이다. 이 코드가 덜 직관적이긴 하지만 좀 더 효율적인 코드를 찾으시는 분들은 읽어보면 좋을 것 같다.

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

12100번: 2048 (Easy)

2048 게임은 아마 다들 해보셨을 거라고 생각한다. 손가락으로 핸드폰을 슉슉 움직여서 2의 배수인 숫자를 최대한 크게 만들면 되는 간단한 게임이다. 실제 게임에서는 한번 움직일 때 마다 새로운 숫자가 등장하지만, 이 문제는 N*N 보드에서 주어진 숫자 이외에는 새로 등장하지 않는다고 가정하고 주어진 숫자들로 5번 움직여서 만들 수 있는 가장 큰 숫자를 출력하는 문제이다.

 

간단하게 백트래킹이라고 생각하고 풀었다. 최대 5번이고 방향이 총 4가지인데 중복이 가능하므로

5P4인 중복 순열이라고 생각했다. 단, 순서를 고려해야 하므로 조합이 될 수는 없다고 판단하고 풀었다. 예를 들어 12345와 54321은 결과값이 다를 수 있다고 생각했다.

 

나 같은 경우는 배열을 미는 Push 함수, 민 배열을 가지고 값을 합치는 Sum 함수 2개를 이용했다.

 

1) Push

 

 

void Push(vector <vector<int>>& tboard, int dir, int r, int c)
{
    if (dir == 0)
    {
        for (int i = 0; i < n; i++)
        {
            if (tboard[i][c] == 0)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (tboard[j][c] != 0)
                    {
                        swap(tboard[i][c], tboard[j][c]);
                        break;
                    }
                }
            }
        }
    }
    else if (dir == 1)
    {
        for (int i = n - 1; i >= 0; i--)
        {
            if (tboard[r][i] == 0)
            {
                for (int j = i - 1; j >= 0; j--)
                {
                    if (tboard[r][j] != 0)
                    {
                        swap(tboard[r][i], tboard[r][j]);
                        break;
                    }
                }
            }
        }
    }
    else if (dir == 2)
    {
        for (int i = n - 1; i >= 0; i--)
        {
            if (tboard[i][c] == 0)
            {
                for (int j = i - 1; j >= 0; j--)
                {
                    if (tboard[j][c] != 0)
                    {
                        swap(tboard[i][c], tboard[j][c]);
                        break;
                    }
                }
            }
        }
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            if (tboard[r][i] == 0)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (tboard[r][j] != 0)
                    {
                        swap(tboard[r][i], tboard[r][j]);
                        break;
                    }
                }
            }
        }
    }
    return;
}

dir은 방향으로 시계방향을 기준으로 해서 시작 방향을 0 = 12시, 1 = 3시, 2 = 6시, 3 = 9시로 생각하고 풀었다.

위쪽 방향일 때를 기준으로 설명해보자면 다음과 같다.

1) 가장 위쪽부터 시작해서 0인 지점을 찾고, 그 0인 지점 다음 인덱스부터 값이 있는 인덱스를 찾는다.

2) 찾았으면 0이었던 지점과 swap한다.

3) 이후 다음 0인 지점을 찾고, 다시 1-2를 반복

 

2) Sum

void Sum(vector <vector<int>>& tboard, int dir, int r, int c)
{
    if (dir == 0)
    {
        for (int i = 0; i < n - 1; i++)
        {
            if (tboard[i][c] == 0) continue;
            if (tboard[i][c] == tboard[i + 1][c])
            {
                tboard[i][c] *= 2;
                tboard[i + 1][c] = 0;
            }
        }
    Push(tboard, dir, r, c);
    }
    else if (dir == 1)
    {
        for (int i = n - 1; i > 0; i--)
        {
            if (tboard[r][i] == 0) continue;
            if (tboard[r][i] == tboard[r][i - 1])
            {
                tboard[r][i] *= 2;
                tboard[r][i - 1] = 0;
            }
        }
        Push(tboard, dir, r, c);
    }
    else if (dir == 2)
    {
        for (int i = n - 1; i > 0; i--)
        {
            if (tboard[i][c] == 0) continue;
            if (tboard[i][c] == tboard[i - 1][c])
            {
                tboard[i][c] *= 2;
                tboard[i - 1][c] = 0;
            }
        }
        Push(tboard, dir, r, c);
    }
    else
    {
        for (int i = 0; i < n - 1; i++)
        {
            if (tboard[r][i] == 0) continue;
            if (tboard[r][i] == tboard[r][i + 1])
            {
                tboard[r][i] *= 2;
                tboard[r][i + 1] = 0;
            }
        }
        Push(tboard, dir, r, c);
    }
    return;
}

Sum도 마찬가지로 4방향으로 나누어서 진행했고, 위쪽을 예로 들어서 설명해보면 다음과 같다.

1) i번째 인덱스와 i+1번째 인덱스의 값이 같은지 확인한다, 이때 0이면 continue

2) 같다면 i번째 인덱스의 값을 *2해주고, i+1번째 인덱스의 값은 0으로 만든다

3) 이를 반복하고 마지막에 Push해준다

Push를 마지막에 해줘야하는데, 중간 인덱스의 값이 0일 수 있어서 밀어주고 끝내야 한다.

 

3) Solve

 

void solve(vector <vector<int>> &tboard, int cnt)
{
    vector <vector<int>> v;
    vector <int> vv(n);
    for (int i = 0; i < n; i++)
        v.push_back(vv);
    if (cnt == 5)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                res = max(res, tboard[i][j]);
 
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                v[j][k] = tboard[j][k];
 
        if (i == 0) // 위, r 움직이고 c 고정
        {
            for (int j = 0; j < n; j++)
            {
                 Push(v, i, 0, j);
                 Sum(v, i, 0, j);
            }
        }
        else if (i == 1) // 오, r 고정하고 c 움직임
        {
            for (int j = n - 1; j >= 0; j--)
            {
                 Push(v, i, j, 0);
                 Sum(v, i, j, 0);
            }
        }
        else if (i == 2) // 아래, r 움직이고 c 고정
        {
            for (int j = n - 1; j >= 0; j--)
            {
                 Push(v, i, 0, j);
                 Sum(v, i, 0, j);
            }
 
        }
        else // 왼쪽, r 고정하고 c 움직임
        {
            for (int j = 0; j < n; j++)
            {
                 Push(v, i, j, 0);
                 Sum(v, i, j, 0);
            }
 
        }
        solve(v, cnt + 1);
    }
}