문제 링크입니다: https://www.acmicpc.net/problem/12100
핸드폰 게임인 2048을 모티브로 만든 문제이지만 게임과는 달리 한번 shift에서 이미 합체된 블록은 더 이상 합체되지 않는 점이 특징이였습니다.
백준 14500번 테트로미노(http://jaimemin.tistory.com/623)처럼 브루트 포스(Brute Force)와 DFS(Depth First Search) 알고리즘을 함께 적용시켜 푸는 문제였습니다.
Board를 적절히 복사해주고 원상복구해주는 것이 핵심이였습니다.
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 20;
int N;
int board[MAX][MAX];
int maxBlock;
void shift(int type)
{
queue<int> q;
//숫자들을 큐에 집어놓고 각 행의
//해당방향 끝에서부터 숫자를 넣기 시작
switch (type)
{
//왼쪽
case 0:
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (board[i][j])
q.push(board[i][j]);
board[i][j] = 0;
}
int idx = 0;
while (!q.empty())
{
int data = q.front();
q.pop();
if (board[i][idx] == 0)
board[i][idx] = data;
else if (board[i][idx] == data)
{
board[i][idx] *= 2;
//시중에 나와있는 게임과 달리 여러번 합쳐지지 않는다
idx++;
}
else
{
idx++;
board[i][idx] = data;
}
}
}
break;
//오른쪽
case 1:
for (int i = 0; i < N; i++)
{
for (int j = N - 1; j >= 0; j--)
{
if (board[i][j])
q.push(board[i][j]);
board[i][j] = 0;
}
int idx = N - 1;
while (!q.empty())
{
int data = q.front();
q.pop();
if (board[i][idx] == 0)
board[i][idx] = data;
else if (board[i][idx] == data)
{
board[i][idx] *= 2;
idx--;
}
else
{
idx--;
board[i][idx] = data;
}
}
}
break;
//위쪽
case 2:
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (board[j][i])
q.push(board[j][i]);
board[j][i] = 0;
}
int idx = 0;
while (!q.empty())
{
int data = q.front();
q.pop();
if (board[idx][i] == 0)
board[idx][i] = data;
else if (board[idx][i] == data)
{
board[idx][i] *= 2;
idx++;
}
else
{
idx++;
board[idx][i] = data;
}
}
}
break;
//아래쪽
case 3:
for (int i = 0; i < N; i++)
{
for (int j = N - 1; j >= 0; j--)
{
if (board[j][i])
q.push(board[j][i]);
board[j][i] = 0;
}
int idx = N - 1;
while (!q.empty())
{
int data = q.front();
q.pop();
if (board[idx][i] == 0)
board[idx][i] = data;
else if (board[idx][i] == data)
{
board[idx][i] *= 2;
idx--;
}
else
{
idx--;
board[idx][i] = data;
}
}
}
break;
}
}
void DFS(int cnt)
{
if (cnt == 5)
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
maxBlock = max(maxBlock, board[i][j]);
return;
}
int copyBoard[MAX][MAX];
//현 보드상태 저장해놓고
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
copyBoard[i][j] = board[i][j];
for (int i = 0; i < 4; i++)
{
shift(i);
DFS(cnt + 1);
//저장해놓은 보드상태로 원상복구
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
board[i][j] = copyBoard[i][j];
}
}
int main(void)
{
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> board[i][j];
DFS(0);
cout << maxBlock << endl;
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2580번 스도쿠 (9) | 2018.07.05 |
|---|---|
| 백준 10845번 큐 (0) | 2018.07.04 |
| 백준 1107번 리모컨 (2) | 2018.07.04 |
| 백준 2251번 물통 (10) | 2018.07.04 |
| 백준 5427번 불 (8) | 2018.07.04 |