Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

백준 12100 [2048(Easy)] - dfs & 브루트포스 본문

코테준비

백준 12100 [2048(Easy)] - dfs & 브루트포스

alstj_성공 2021. 10. 4. 20:01

출처 : https://www.acmicpc.net/problem/12100

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

 

#include <iostream>
#include <queue>
using namespace std;
int board[21][21];
int copy_board[21][21];
int N, Max = 0;
int Select[5];
void Copy()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
copy_board[i][j] = board[i][j];
}
}
}
void Shift()
{
//5번 이동이니 for문 들어가기 전에 복사
Copy();
for (int i = 0; i < 5; i++)
{
queue<int> q;
switch (Select[i])
{
case 0: //East
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (copy_board[i][j] != 0)
q.push(copy_board[i][j]);
copy_board[i][j] = 0;
}
int index = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (copy_board[i][index] == 0)
copy_board[i][index] = cur;
else if (copy_board[i][index] == cur)
{
copy_board[i][index++] *= 2; //합치는거 1번밖에 안되니까
}
else
{
copy_board[i][++index] = cur;
}
}
}
break;
case 1: //West
for (int i = 0; i < N; i++)
{
for (int j = N - 1; j >= 0; j--)
{
if (copy_board[i][j] != 0)
q.push(copy_board[i][j]);
copy_board[i][j] = 0;
}
int index = N - 1;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (copy_board[i][index] == 0)
copy_board[i][index] = cur;
else if (copy_board[i][index] == cur)
{
copy_board[i][index--] *= 2;
}
else
{
copy_board[i][--index] = cur;
}
}
}
break;
case 2: //North
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
if (copy_board[i][j] != 0)
q.push(copy_board[i][j]);
copy_board[i][j] = 0;
}
int index = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (copy_board[index][j] == 0)
copy_board[index][j] = cur;
else if (copy_board[index][j] == cur)
{
copy_board[index++][j] *= 2;
}
else
{
copy_board[++index][j] = cur;
}
}
}
break;
case 3: //South
for (int j = 0; j < N; j++)
{
for (int i = N - 1; i >= 0; i--)
{
if (copy_board[i][j] != 0)
q.push(copy_board[i][j]);
copy_board[i][j] = 0;
}
int index = N - 1;
while (!q.empty())
{
int cur = q.front();
q.pop();
if (copy_board[index][j] == 0)
copy_board[index][j] = cur;
else if (copy_board[index][j] == cur)
{
copy_board[index--][j] *= 2;
}
else
{
copy_board[--index][j] = cur;
}
}
}
break;
}
}
}
void Find_Max()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (copy_board[i][j] > Max)
Max = copy_board[i][j];
}
}
}
void dfs(int cnt)
{
if (cnt == 5)
{
Shift();
Find_Max();
return;
}
//direction
for (int i = 0; i < 4; i++)
{
Select[cnt] = i;
dfs(cnt + 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> board[i][j];
}
}
dfs(0);
cout << Max << '\n';
return 0;
}
view raw 12100.cpp hosted with ❤ by GitHub

첫번째 시도 

- queue를 사용하지 않음. -> 자꾸 틀렸다고 나오는데 원인을 찾지 못함.

두번째 시도

- queue를 사용하여 해결

 

<순서>

1. 배열을 이용하여 5번의 이동방향을 정해주기

2. 5번의 이동방향이 정해졌다면 shift()함수를 통해 동서남북의 case 각각 걸어주기

-> 이동 시작 전에 원본 배열 복사. for문 안에서 copy()하면 매번 배열이 바뀌기 때문에 틀림

-> 0이 아니라면 q에 집어넣고 모든 copy_board 값은 0으로 바꿔줌.

-> 0이 아닌 원소들을 차례대로 copy_board에 집어넣어줌

( 1번밖에 합치지 못하는 것은 else if(copy_board[i][j] == cur) 문을 통해 해결) -> 같다면 계산후 머무르지 않고 index증가)

( 계산 전 이동부분과 계산 후 이동부분은  q에 집어넣은 후 q에 있는 것을 차례로 copy_board에 집어넣어주면서 해결)

3. 5번의 이동이 끝났다면 Find_Max() 함수를 통해 max값을 찾아줌.