(백준 c++)12100. 2048(Easy)

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

12100번: 2048 (Easy)

 

DFS를 이용한 완전 탐색.

 

우선 N x N 크기의 보드를 만든 후 숫자를 저장한다.

이후 for문을 이용하여 상,하,좌,우로 움직이는데, 이를 dfs 함수로 한다.

dfs 함수는 (방향, 보드, 움직인 횟수)를 매개변수로 넘겨준다.

 

dfs()

우선 dfs 종료 조건을 정의한다.

count == 5면 board를 순회하여 answer보다 큰 숫자를 갱신한 후 return.

 

종료조건이 아니라면 현재 board를 direct의 방향으로 움직인다.

direct는 0, 1, 2, 3 중 하나이며, 각각 상, 하, 좌, 우로 움직인다.

보드를 움직이는 것은 큐를 이용한다.

위, 아래로 움직인 경우와 좌, 우로 움직인 경우는 이중 for문에서 i와 j의 위치가 같으며, 시작하는 방향만 다르다.

이에 유의하며 큐에 숫자를 넣어주고,

i번째 행에서 같은 수는 더해주면서 보드를 채운다.

만약 채우려고 하는 칸이 0이라면 큐의 front()를 채운다.

0이 아니라면 현재 칸과 큐의 front()를 같은지 비교하여, 같다면 큐를 pop() 한 후 다음 칸으로 넘어간다.

이 외에 조건이라면 무조건 다음 칸으로 이동.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int answer = 0;
int N;

void dfs(int direct, vector<vector<int>> board, int count) {
	vector<vector<int>> newBoard(N, vector<int>(N, 0));
	queue<int> q;
	
	if(count == 5){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				answer = answer < board[i][j] ? board[i][j] : answer;
			}
		}
		
		return;
	}
	
	switch(direct){
		case 0:
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					if(board[j][i]){
						q.push(board[j][i]);	
					}
				}
				
				for(int j = 0; j < N; j++){
					while(!q.empty()){
						if(newBoard[j][i] == 0){
							newBoard[j][i] = q.front();
							q.pop();
							continue;
						} else if(newBoard[j][i] == q.front()) {
							newBoard[j][i] += q.front();
							q.pop();
						}
						
						break;
					}
				}
			}
			
			break;
		
		case 1:
			for(int i = 0; i < N; i++){
				for(int j = N - 1; j >= 0; j--){
					if(board[j][i]){
						q.push(board[j][i]);
					}
				}
				
				for(int j = N - 1; j >= 0; j--){
					while(!q.empty()){
						if(newBoard[j][i] == 0){
							newBoard[j][i] = q.front();
							q.pop();
							continue;
						} else if(newBoard[j][i] == q.front()) {
							newBoard[j][i] += q.front();
							q.pop();
						} 
						
						break;
					}
				}
			}
			
			break;
		
		case 2:
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					if(board[i][j]){
						q.push(board[i][j]);
					}
				}
				
				for(int j = 0; j < N; j++){
					while(!q.empty()){
						if(newBoard[i][j] == 0){
							newBoard[i][j] = q.front();
							q.pop();
							continue;
						} else if(newBoard[i][j] == q.front()) {
							newBoard[i][j] += q.front();
							q.pop();
						}
						
						break;
					}
				}
			}
			
			break;
		
		case 3:
			for(int i = 0; i < N; i++){
				for(int j = N - 1; j >= 0; j--){
					if(board[i][j]){
						q.push(board[i][j]);
					}
				}
				
				for(int j = N - 1; j >= 0; j--){
					while(!q.empty()){
						if(newBoard[i][j] == 0){
							newBoard[i][j] = q.front();
							q.pop();
							continue;
						} else if(newBoard[i][j] == q.front()) {
							newBoard[i][j] += q.front();
							q.pop();
						}
						
						break;
					}
				}
			}
			
			break;
	}
	
	for(int i = 0; i < 4; i++){
		dfs(i, newBoard, count + 1);
	}
}

int main() {
	cin >> N;

	vector<vector<int>> board(N, vector<int>(N, 0));
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> board[i][j];
		}
	}
	
	for(int i = 0; i < 4; i++){
		dfs(i, board, 0);
	}
	
	cout << answer;
	
	return 0;
}