12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
이것저것 생각할 게 많아서 재미있는 문제였다.
알고리즘은 다음과 같다.
한번 움직이는데 가능한 경우의 수는 위 아래 왼쪽 오른쪽 4개의 경우가 있으며 최대 5번 움직이기 때문에 움직일 수 있는 모든 경우의 수를 다해보고, 움직인 횟수가 5번이 됐을 때를 기저사례로 추가하여 보드의 최댓값을 변수에 저장해주면 된다.
같은 숫자일때 합쳐지는 것과 움직이는 방향에 따라 합쳐지는 우선순위가 다르다는 점을 구현하기 위해 Queue를 사용하였다.
위로 올리는 경우를 예로 들면,
1. 동일한 x좌표 상에서 y좌표만 0부터 N-1까지 차례대로 큐에 넣는다.
2. 큐의 첫번째 원소를 first, 두번째 원소를 second에 저장하고 저장한 원소는 제거한다.
if (0은 빈 칸을 뜻하므로 first또는 second에 0이 저장되있다면 다시 2번 과정을 반복한다.)
if (큐가 비어있는지 확인하고 비어있다면 위 과정은 건너뛴다.)
3. first와 second가 같은 숫자라면 first * 2한 값을 board[0][x]에 넣어주고, first = 0, second = 0 으로 바꿔준다.
다른 숫자라면 first를 board[0][x]에 넣어주고 first = second, second = 0 으로 바꿔준다.
4. y좌표가 N-1이 될 때까지 y를 1 증가시키면서 2, 3번 과정을 반복한다.
5. x좌표가 N-1이 될 때까지 x를 1증가시키면서 1번~4번 과정을 반복한다.
위의 과정을 위, 아래, 왼쪽, 오른쪽의 경우에 대해 각각 다르게 구현해준 다음, 모든 경우의 수를 완전탐색하면 원하는 결과를 얻을 수 있다.
지금 보여드리는 코드는 중복되는 코드를 최대한 줄여놓은 코드입니다.
이해하기 힘드신분들을 위해 줄이기 전 코드도 함께 첨부해드릴게요.
더보기
|
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int board[21][21];
int maxLen;
int maxNum = -987654321;
int max(int a, int b) { return a > b ? a : b; }
void Solution(int moveCnt); // 전방선언
void AddBoard(queue<int>& tempQ, int here, int type)
{
int fir = 0, sec = 0;
for (int i = 0; i < maxLen; i++)
{
while (!tempQ.empty())
{
int n = tempQ.front();
tempQ.pop();
if (fir == 0) fir = n;
else if (sec == 0) sec = n;
if (fir != 0 && sec != 0) break;
}
switch (type)
{
case 0: // 위로 올렸을 때
if (fir == sec)
{
board[i][here] = fir * 2;
fir = 0, sec = 0;
}
else
{
board[i][here] = fir;
fir = sec, sec = 0;
}
break;
case 1: // 아래로 내렸을 때
if (fir == sec)
{
board[maxLen - 1 - i][here] = fir * 2;
fir = 0, sec = 0;
}
else
{
board[maxLen - 1 - i][here] = fir;
fir = sec, sec = 0;
}
break;
case 2: // 오른쪽으로 밀었을 때
if (fir == sec)
{
board[here][i] = fir * 2;
fir = 0, sec = 0;
}
else
{
board[here][i] = fir;
fir = sec, sec = 0;
}
break;
case 3: // 왼쪽으로 밀었을 때
if (fir == sec)
{
board[here][maxLen - 1 - i] = fir * 2;
fir = 0, sec = 0;
}
else
{
board[here][maxLen - 1 - i] = fir;
fir = sec, sec = 0;
}
}
}
}
void MovingBoard(int type, int moveCnt)
{
queue<int> tempQ;
switch (type)
{
case 0: // 위로 올렸을 때
for (int i = 0; i < maxLen; i++)
{
for (int j = 0; j < maxLen; j++)
tempQ.push(board[j][i]);
AddBoard(tempQ, i, type);
}
Solution(moveCnt + 1);
break;
case 1: // 아래로 내렸을 때
for (int i = 0; i < maxLen; i++)
{
for (int j = maxLen - 1; j >= 0; j--)
tempQ.push(board[j][i]);
AddBoard(tempQ, i, type);
}
Solution(moveCnt + 1);
break;
case 2: // 오른쪽으로 밀었을 때
for (int i = 0; i < maxLen; i++)
{
for (int j = 0; j < maxLen; j++)
tempQ.push(board[i][j]);
AddBoard(tempQ, i, type);
}
Solution(moveCnt + 1);
break;
case 3: // 왼쪽으로 밀었을 때
for (int i = 0; i < maxLen; i++)
{
for (int j = maxLen - 1; j >= 0; j--)
tempQ.push(board[i][j]);
AddBoard(tempQ, i, type);
}
Solution(moveCnt + 1);
break;
}
}
void Solution(int moveCnt)
{
if (moveCnt == 5)
{
for (int i = 0; i < maxLen; i++)
for (int j = 0; j < maxLen; j++)
maxNum = max(maxNum, board[i][j]);
return;
}
int temp[21][21];
memcpy(temp, board, sizeof(board));
int type = 4;
while (type--) // 4번 반복(상하좌우)
{
MovingBoard(type, moveCnt);
memcpy(board, temp, sizeof(board));
}
}
int main(void)
{
cin >> maxLen;
int n;
for (int i = 0; i < maxLen; i++)
for (int j = 0; j < maxLen; j++)
cin >> board[i][j];
Solution(0);
cout << maxNum << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
|
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int board[21][21];
int maxLen;
int maxNum = -987654321;
int max(int a, int b) { return a > b ? a : b; }
void Solution(int moveCnt); // 전방선언
void AddNumber(int& fir, int& sec, int col, int row)
{
if (fir == sec)
{
board[col][row] = fir * 2;
fir = 0, sec = 0;
}
else
{
board[col][row] = fir;
fir = sec, sec = 0;
}
}
void AddBoard(queue<int>& tempQ, int here, int type)
{
int fir = 0, sec = 0;
for (int i = 0; i < maxLen; i++)
{
while (!tempQ.empty())
{
int n = tempQ.front();
tempQ.pop();
if (fir == 0) fir = n;
else if (sec == 0) sec = n;
if (fir != 0 && sec != 0) break;
}
switch (type)
{
case 0: // 위로 올렸을 때
AddNumber(fir, sec, i, here);
break;
case 1: // 아래로 내렸을 때
AddNumber(fir, sec, maxLen - 1 - i, here);
break;
case 2: // 오른쪽으로 밀었을 때
AddNumber(fir, sec, here, i);
break;
case 3: // 왼쪽으로 밀었을 때
AddNumber(fir, sec, here, maxLen - 1 - i);
break;
}
}
}
void Moving(int start, int end, int type, int moveCnt)
{
queue<int> tempQ;
for (int i = 0; i < maxLen; i++)
{
if (type == 0 || type == 2) // 위로 올렸을 때 || 오른쪽으로 밀었을 때
for (int j = start; j < end; j++)
{
if (type == 0)
tempQ.push(board[j][i]);
else
tempQ.push(board[i][j]);
}
else // 아래로 내렸을 때 || 왼쪽으로 밀었을 때
for (int j = start; j >= end; j--)
{
if (type == 1)
tempQ.push(board[j][i]);
else
tempQ.push(board[i][j]);
}
AddBoard(tempQ, i, type);
}
Solution(moveCnt + 1);
}
void MovingBoard(int type, int moveCnt)
{
if (type == 0 || type == 2)
Moving(0, maxLen, type, moveCnt);
else
Moving(maxLen - 1, 0, type, moveCnt);
}
void Solution(int moveCnt)
{
if (moveCnt == 5) // 기저사례. 5번 이동했다면 보드에서 제일 큰 수 저장
{
for (int i = 0; i < maxLen; i++)
for (int j = 0; j < maxLen; j++)
maxNum = max(maxNum, board[i][j]);
return;
}
int temp[21][21];
memcpy(temp, board, sizeof(board)); // 바뀌기 전 보드 저장
int type = 4;
while (type--) // 4번 반복(상하좌우)
{
MovingBoard(type, moveCnt);
memcpy(board, temp, sizeof(temp)); // 복사해놨던 보드로 다시 바꿈
}
}
int main(void)
{
cin >> maxLen;
for (int i = 0; i < maxLen; i++)
for (int j = 0; j < maxLen; j++)
cin >> board[i][j];
Solution(0);
cout << maxNum << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 14day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 10448: 유레카 이론 (c++) (0) | 2020.04.21 |
|---|---|
| 백준 1748번: 수 이어 쓰기 1 (C++) (0) | 2020.04.20 |
| 백준 15683번: 감시 (C++) (0) | 2020.04.18 |
| 백준 1065번: 한수 (0) | 2020.04.17 |
| 백준 15686번: 치킨 배달 (C++) (0) | 2020.04.15 |