끄적끄적
백준 12100 [2048(Easy)] - dfs & 브루트포스 본문
출처 : https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
첫번째 시도
- 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값을 찾아줌.
'코테준비' 카테고리의 다른 글
프로그래머스 sql [없어진 기록] (0) | 2021.10.07 |
---|---|
백준 2110 [공유기 설치] - 이분탐색 (0) | 2021.10.06 |
프로그래머스 level 3 [징검다리 건너기] (0) | 2021.10.01 |
백준 11727 [2xn 타일링 2] -dp (0) | 2021.09.27 |
백준 11726 [2×n 타일링] -dp (0) | 2021.09.27 |