되면한다
백준 12100. 2048 (Easy) 본문
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
입력값이 주어졌을 때, 2048 게임룰로 게임을 진행하고, 블록의 최댓값을 출력한다.
1. 특징
1) 백트래킹
2) 구현
2. 구현 포인트
1) 백트래킹: 문제 조건으로 최대 다섯번(좌,우, 상, 하)을 움직일 수 있다고 했다. 좌좌좌좌좌 -> 좌좌좌좌우-> ... -> 하하하하하. 이 경우를 찾아내기 위해 백트래킹을 사용했다.
2) 좌, 우, 상, 하로 움직였을 때: 1) 움직이려고 하는 방향으로 0을 없애면서 숫자를 붙인다. 2) 연속해서 나타난 두수를 더하고 움직이려는 방향으로 미뤄준다. 3) 다시한번 1을 진행한다. (왜인지 2번만으로 오류가 나서 3번을 진행)
2-1) 움직이려고 하는 방향(UP)으로 0을 없애면서 숫자를 붙이는 코드
for(int j = 0; j < n; j++)
{
int prev = tboard[0][j];
for(int i = 0; i < n; i++)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curi = i;
while(tboard[curi-1][j] == 0 && curi - 1>= 0)
{
curi--;
}
tboard[curi][j] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
2-2) 연속한 두수를 더하는 코드 (UP)
연속한 수가 나타나면 두번째 좌표에 값을 2곱하고, 첫번째 수 좌표값은 0으로 만든다.
for(int j = 0; j < n; j++) //열기준
{
int prev = tboard[0][j];
for(int i = 1; i < n; i++)
{
if(tboard[i][j] == prev)
{
int curi = i;
tboard[curi-1][j] = 0;
while(tboard[curi-1][j] == 0 && curi - 1>= 0)
{
curi--;
}
tboard[curi][j] = tboard[i][j] * 2;
tboard[i][j] = 0;
prev = -1;
continue;
}
else
{
prev = tboard[i][j];
}
}
}
3. 코드
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <set>
#include <cstring>
#include <string>
#include <stdio.h>
#include <limits.h>
using namespace std;
int n;
int board[22][22];
int tboard[22][22];
int arr[5];
int ans;
void Up()
{
for(int j = 0; j < n; j++)
{
int prev = tboard[0][j];
for(int i = 0; i < n; i++)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curi = i;
while(tboard[curi-1][j] == 0 && curi - 1>= 0)
{
curi--;
}
tboard[curi][j] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
for(int j = 0; j < n; j++) //열기준
{
int prev = tboard[0][j];
for(int i = 1; i < n; i++)
{
if(tboard[i][j] == prev)
{
int curi = i;
tboard[curi-1][j] = 0;
while(tboard[curi-1][j] == 0 && curi - 1>= 0)
{
curi--;
}
tboard[curi][j] = tboard[i][j] * 2;
tboard[i][j] = 0;
prev = -1;
continue;
}
else
{
prev = tboard[i][j];
}
}
}
for(int j = 0; j < n; j++)
{
int prev = tboard[0][j];
for(int i = 0; i < n; i++)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curi = i;
while(tboard[curi-1][j] == 0 && curi - 1>= 0)
{
curi--;
}
tboard[curi][j] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
}
void Down()
{
for(int j = 0; j < n; j++)
{
int prev = tboard[n-1][j];
for(int i = n-1; i >= 0; i--)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curi = i;
while(tboard[curi+1][j] == 0 && curi + 1 <= n - 1)
{
curi++;
}
tboard[curi][j] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
for(int j = 0; j < n; j++) //열기준
{
int prev = tboard[n-1][j];
for(int i = n-2; i >= 0; i--)
{
if(tboard[i][j] == prev)
{
int curi = i;
tboard[curi+1][j] = 0;
while(tboard[curi+1][j] == 0 && curi + 1 <= n - 1)
{
curi++;
}
tboard[curi][j] = tboard[i][j] * 2;
tboard[i][j] = 0;
prev = -1;
continue;
}
else
{
prev = tboard[i][j];
}
}
}
for(int j = 0; j < n; j++)
{
int prev = tboard[n-1][j];
for(int i = n-1; i >= 0; i--)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curi = i;
while(tboard[curi+1][j] == 0 && curi + 1 <= n - 1)
{
curi++;
}
tboard[curi][j] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
}
void Left()
{
for(int i = 0; i < n; i++)
{
int prev = tboard[i][0];
for(int j = 0; j < n; j++)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curj = j;
while(tboard[i][curj - 1] == 0 && curj -1 >= 0)
{
curj--;
}
tboard[i][curj] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
for(int i = 0; i < n; i++)
{
int prev = tboard[i][0];
for(int j = 1; j < n; j++)
{
if(tboard[i][j] == prev)
{
int curj = j;
tboard[i][curj-1] = 0;
while(tboard[i][curj-1] == 0 && curj - 1 >= 0)
{
curj--;
}
tboard[i][curj] = tboard[i][j] * 2;
tboard[i][j] = 0;
prev = -1;
continue;
}
else
{
prev = tboard[i][j];
}
}
}
for(int i = 0; i < n; i++)
{
int prev = tboard[i][0];
for(int j = 0; j < n; j++)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curj = j;
while(tboard[i][curj - 1] == 0 && curj -1 >= 0)
{
curj--;
}
tboard[i][curj] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
}
void Right()
{
for(int i = 0; i < n; i++)
{
int prev = tboard[i][n-1];
for(int j = n-2; j >= 0; j--)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curj = j;
while(tboard[i][curj + 1] == 0 && curj +1 <= n-1)
{
curj++;
}
tboard[i][curj] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
for(int i = 0; i < n; i++)
{
int prev = tboard[i][n-1];
for(int j = n-2; j >= 0; j--)
{
if(tboard[i][j] == prev)
{
int curj = j;
tboard[i][curj+1] = 0;
while(tboard[i][curj+1] == 0 && curj + 1 <= n -1)
{
curj++;
}
tboard[i][curj] = tboard[i][j] * 2;
tboard[i][j] = 0;
prev = -1;
continue;
}
else
{
prev = tboard[i][j];
}
}
}
for(int i = 0; i < n; i++)
{
int prev = tboard[i][n-1];
for(int j = n-2; j >= 0; j--)
{
if(prev == 0 && tboard[i][j] > 0)
{
int curj = j;
while(tboard[i][curj + 1] == 0 && curj +1 <= n-1)
{
curj++;
}
tboard[i][curj] = tboard[i][j];
tboard[i][j] = 0;
}
prev = tboard[i][j];
}
}
}
void movefunc()
{
for(int i = 0; i < 5; i++)
{
if(arr[i] == 0) // 좌로 밀기
{
Left();
}
if(arr[i] == 1) // 우로 밀기
{
Right();
}
if(arr[i] == 2) // 위로 밀기
{
Up();
}
if(arr[i] == 3) // 아래로 밀기
{
Down();
}
}
}
void Init()
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
tboard[i][j] = board[i][j];
}
}
}
int calMax()
{
int val = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
val = max(val, tboard[i][j]);
}
}
return val;
}
void func(int cur)
{
if(cur == 5)
{
Init();
movefunc();
ans = max(calMax(), ans);
return;
}
for(int i = 0; i < 4; i++) //좌 우 위 아래
{
arr[cur] = i;
func(cur + 1);
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> board[i][j];
}
}
func(0);
cout << ans;
}'코딩테스트준비 > 다시볼문제' 카테고리의 다른 글
| 백준 1431. 시리얼 번호 (0) | 2023.07.06 |
|---|---|
| 백준 13335. 트럭 (구현) (0) | 2023.07.05 |
| 백준 20166. 문자열 지옥에 빠진 호석 (해시) (0) | 2023.07.01 |
| 백준 18808. 스티커 붙이기 (구현) (0) | 2023.07.01 |
| 백준 2531. 회전 초밥 (투포인터) (0) | 2023.06.27 |
Comments