이번에는 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;
}