[C++] 백준(BOJ) - 12100 : 2048 (easy)
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
알고리즘
- 구현
- 완전탐색
풀이
- 90도 회전 알고리즘
i, j => n-j-i, i
- Temp 배열 사용
- 같으면 추가
- 다르면 넘어가기
코드
// BOJ-12100 : 2048 (easy)
#include <bits/stdc++.h>
using namespace std;
int n, res;
struct Board {
int a[24][24];
// 1. 배열이 90도 회전하는 로직
void Rotate90()
{
int tmp[24][24];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) {
tmp[i][j] = a[n - j - 1][i];
}
}
memcpy(a, tmp, sizeof(a));
}
// 2. 메인로직
/// <summary>
/// [2][0][2][0] => [4][0][0][0]
/// </summary>
void MoveLogic()
{
int tmp[24][24];
for (int i = 0; i < n; i++)
{
int c = -1, d = 0;
for (int j = 0; j < n; j++)
{
if (a[i][j] == 0) continue; // 0이면 넘어가고
if (d && a[i][j] == tmp[i][c]) tmp[i][c] *= 2, d = 0;
else {
tmp[i][++c] = a[i][j];
d = 1;
}
}
for (c++; c < n; c++) tmp[i][c] = 0;
}
memcpy(a, tmp, sizeof(a));
}
void GetMax()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
res = max(res, a[i][j]);
}
}
}
};
// 완전탐색
void go(Board b, int here)
{
// 기저사례
if (here == 5)
{
b.GetMax();
return;
}
for (int i = 0; i < 4; i++)
{
Board d = b;
d.MoveLogic();
go(d, here + 1);
b.Rotate90(); // 네방향 탐색 구현
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
Board bd;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{
cin >> bd.a[i][j];
}
}
go(bd, 0);
cout << res << '\n';
return 0;
}
평가
- 배열의 90도 회전 알고리즘 필수적으로 기억
- i, j <= n-j-1, i
- 구조체를 활용한 메소드 구현
- 완전탐색을 위한 기저조건, for문을 활용해서 90도 회전 알고리즘 재귀함수 아래에 넣어서 구현
