Array ( )

2016 하반기 삼성 SW 역량 테스트 - 2048(Easy)

2018-12-02 23:45:38 | 조회수 5373



이번에는 2016년 하반기 삼성 SW 역량 테스트 문제를 확인해 보겠습니다. 복원된 문제의 제목은 2048(Easy) 입니다. 2048은 중독성 있는 미니게임으로 특정 방향으로 이동을 할 때 같은 2개의 블록이 합쳐져 숫자가 2배가 되는 게임입니다.


이 문제에서는 블록이 주어져 있을 때, 5번의 이동으로 최대한 큰 숫자를 만들어내는 프로그램을 짜야합니다. 이 문제에서는 5번을 이동하여가 핵심 키워드라고 볼 수 있습니다. 제한이 비교적 강하게 걸린 상황에서, 총 4가지의 방향을 선택할 수 있으므로, $4^5 = 1024$ 가지의 방법을 모두 시도해볼 수 있다는 점을 알 수 있습니다.


그리고 5번을 시도하는 과정에서 가장 큰 숫자를 파악해야 하므로, 저는 큐를 이용하여 횟수와 보드의 상태를 저장할 수 있는 클래스를 짜고, 그 클래스가 생성되는 순서대로 꺼내어 다음 이동을 할 수 있는 형태로 프로그램을 설계하였습니다. 즉, 최초 보드 상태에서 상,하,좌,우 로 이동한 결과를 각각 큐에 push 하면, 그 다음에는 상 으로 이동한 상태에서 또 다시 상,하,좌,우 ... 를 시도할 수 있는 형태입니다. 이렇게 하더라도 아까 말했듯 1024가지 이상의 경우의 수는 나오지 않으므로, 빠르게 테스트할 수 있습니다.


저 같은 경우는 상,하,좌,우 의 case를 나누어 각각을 모두 for문으로 설계하였더니 소스코드가 많이 길어졌습니다. 최적화를 한다면 더 짧아질 수도 있을 것입니다.


※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include<iostream>
#include<queue>
using namespace std;

class Board
{
public:
    int sz, count, w[21][21];
    bool tmp[21][21];
    Board() { count = 0; }
    Board(int a) : sz(a)
    {
        count = 0;
        for (int i = 0; i < sz; i++)
            for (int j = 0; j < sz; j++)
                w[i][j] = tmp[i][j] = 0;
    }
};
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
void move(Board &b1, Board &b2, int dir)
{
    for (int i = 0; i < b1.sz; i++)
        for (int j = 0; j < b1.sz; j++)
            b2.w[i][j] = b1.w[i][j], b2.tmp[i][j] = true;
    if (dir == 0)
    {
        for(int j=0; j<b2.sz; j++)
            for (int i = 1; i < b2.sz; i++)
            {
                if (!b2.w[i][j]) continue;
                int t = i - 1;
                while (t >= 0 && !b2.w[t][j])
                {
                    b2.w[t][j] = b2.w[t + 1][j];
                    b2.w[t + 1][j] = 0;
                    t--;
                }
                if (t>=0 && b2.tmp[t][j] && b2.w[t][j] == b2.w[t + 1][j])
                {
                    b2.w[t][j] *= 2;
                    b2.w[t + 1][j] = 0;
                    b2.tmp[t][j] = false;
                }
            }
    }
    if (dir == 1)
    {
        for (int i = 0; i<b2.sz; i++)
            for (int j = b2.sz-2; j >=0; j--)
            {
                if (!b2.w[i][j]) continue;
                int t = j + 1;
                while (t < b2.sz && !b2.w[i][t])
                {
                    b2.w[i][t] = b2.w[i][t - 1];
                    b2.w[i][t - 1] = 0;
                    t++;
                }
                if (t < b2.sz && b2.tmp[i][t] && b2.w[i][t] == b2.w[i][t - 1])
                {
                    b2.w[i][t] *= 2;
                    b2.w[i][t - 1] = 0;
                    b2.tmp[i][t] = false;
                }
            }
    }
    if (dir == 2)
    {
        for (int j = 0; j<b2.sz; j++)
            for (int i = b2.sz-2; i >=0; i--)
            {
                if (!b2.w[i][j]) continue;
                int t = i + 1;
                while (t < b2.sz && !b2.w[t][j])
                {
                    b2.w[t][j] = b2.w[t - 1][j];
                    b2.w[t - 1][j] = 0;
                    t++;
                }
                if (t < b2.sz && b2.tmp[t][j] && b2.w[t][j] == b2.w[t - 1][j])
                {
                    b2.w[t][j] *= 2;
                    b2.w[t - 1][j] = 0;
                    b2.tmp[t][j] = false;
                }
            }
    }
    if (dir == 3)
    {
        for (int i = 0; i<b2.sz; i++)
            for (int j = 1; j < b2.sz; j++)
            {
                if (!b2.w[i][j]) continue;
                int t = j - 1;
                while (t >= 0 && !b2.w[i][t])
                {
                    b2.w[i][t] = b2.w[i][t + 1];
                    b2.w[i][t + 1] = 0;
                    t--;
                }
                if (t >= 0 && b2.tmp[i][t] && b2.w[i][t] == b2.w[i][t + 1])
                {
                    b2.w[i][t] *= 2;
                    b2.w[i][t + 1] = 0;
                    b2.tmp[i][t] = false;
                }
            }
    }
}
int main()
{
    int n, ans = 0;
    queue<Board> q;

    cin >> n;
    Board st(n);

    for(int i=0; i<n; i++)
        for (int j = 0; j < n; j++)
            cin >> st.w[i][j];
    
    q.push(st);
    while (!q.empty())
    {
        Board here = q.front();
        
        q.pop();
        for (int i = 0; i < here.sz; i++)
            for (int j = 0; j < here.sz; j++)
                if (ans < here.w[i][j]) ans = here.w[i][j];

        if (here.count == 5) continue;
        Board there(n);
        there.count = here.count + 1;
        for (int i = 0; i < 4; i++)
        {
            move(here, there, i);
            q.push(there);
        }
    }
    cout << ans;
}


2016 하반기 삼성 SW 역량 테스트 - 2048(Easy) - 알고리즘닷컴
32 개의 글