[백준 12100번] 2048(Easy) C++

백준 12100번 2048(Easy)
https://www.acmicpc.net/problem/12100

DFS를 이용한 완전탐색 구현 문제였다. 깊이가 5가 될 때 보드 위의 숫자 중 최대값을 찾아주었는데 계속 오답 처리가 되었다. 질문 검색을 찾아보니 5로 가는 동안에도 매번 최대값을 찾아줘야 한다고 한다(그런데 최대값은 더 이상 합쳐지지 않아서 결국 5번째에 남는 것 아닌가? 이 부분은 잘 모르겠다).

https://jaimemin.tistory.com/660
이 블로그의 코드를 참조했다.

풀이 방법

1.

switch 문을 이용하여 왼쪽, 오른쪽, 위, 아래 각각의 경우에 맞게 움직이는 shift라는 함수를 작성한다.

[shift 과정]
Queue를 이용하여 각 행의 0이 아닌 원소를 저장하고 그 자리에 0을 대입한다. 이동하려는 쪽부터 숫자를 넣어주며 같은 숫자가 나왔을 경우 최대 2개의 같은 숫자에 한해서 합쳐준다.

2.

DFS 함수를 작성한다.

깊이가 5가 되면 return문으로 함수를 종료시킨다. depth가 5보다 작다면, 기존 보드를 저장하고, for문으로 4가지 방향에 대해 shift를 시킨 후에 2중 for문으로 보드 안에서 최대값을 탐색한다. 그 이후 다시 DFS 함수를 호출한다. DFS 함수가 끝나고 나왔을 때, 저장해두었던 기존 보드를 다시 입력해주어서 원상 복구 시켜준다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int n;
int board[21][21];
int mxN = 0;


void shift(int num) {
	queue<int> q;

	switch(num) {
		// left
		case 0:
			for(int i=1;i<=n;++i) {
				for(int j=1;j<=n;++j) {
					if(board[i][j] != 0) {
						q.push(board[i][j]);
					}
					board[i][j] = 0;
				}
				int idx = 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;

		// right
		case 1:
			for(int i=1;i<=n;++i) {
				for(int j=n;j>=1;--j) {
					if(board[i][j] != 0) {
						q.push(board[i][j]);
					}
					board[i][j] = 0;
				}
				int idx = n;

				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;

		// up
		case 2:
			for(int j=1;j<=n;++j) {
				for(int i=1;i<=n;++i) {
					if(board[i][j] != 0) {
						q.push(board[i][j]);
					}
					board[i][j] = 0;
				}
				int idx = 1;

				while(!q.empty()) {
					int data = q.front();
					q.pop();

					if(board[idx][j] == 0) {
						board[idx][j] = data;
					} else if(board[idx][j] == data) {
						board[idx][j] *= 2;
						idx++;
					} else {
						idx++;
						board[idx][j] = data;
					}
				}
			}
			break;

		// down
		case 3:
			for(int j=1;j<=n;++j) {
				for(int i=n;i>=1;--i) {
					if(board[i][j] != 0) {
						q.push(board[i][j]);
					}
					board[i][j] = 0;
				}
				int idx = n;

				while(!q.empty()) {
					int data = q.front();
					q.pop();

					if(board[idx][j] == 0) {
						board[idx][j] = data;
					} else if(board[idx][j] == data) {
						board[idx][j] *= 2;
						idx--;
					} else {
						idx--;
						board[idx][j] = data;
					}
				}
			}
	}
}

void dfs(int depth) {
	if(depth == 5) {

		return;
	}

	int newBoard[21][21];
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			newBoard[i][j] = board[i][j];
		}
	}

	for(int i=0;i<4;++i) {
		shift(i);
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				if(board[i][j] > mxN) {
					mxN = board[i][j];
				}
			}
		}

		dfs(depth + 1);

		for(int j=1;j<=n;++j) {
			for(int k=1;k<=n;++k) {
				board[j][k] = newBoard[j][k];
			}
		}
	}
}

int main(void) {
	ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	cin>>n;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			cin >> board[i][j];
		}
	}


	dfs(0);

	cout << mxN << "\n";

	return 0;
}