[백준 12100][완전탐색][C++] 2048(Easy)

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

12100번: 2048 (Easy)

당직 서다 심심해서 2048 만들고 아 이런 문제 있었는데 해서 풀어본 문제입니다 히히;

 

n이 20밖에 안돼서 완전탐색으로 충분히 풀 수 있는 문제였습니다. 보드의 값들을 이동시킬 때(갱신시킬 때), 각 행/열을 먼저 deque에 push_back으로 다 넣어주고 이동방향(위로 갈 경우 위에서부터) front에서부터 하나씩 꺼내주며 갱신해줬습니다. 값이 합쳐지는 경우는 하나 꺼낼 때 deque의 다음 값과 비교해서 같으면 deque의 다음 값도 꺼내버리고 2를 곱해줬습니다.

구현문제라 그런지 간단하지만서도 풀 때 이것저것 생각하면서 스트레스 받게되는 문제였네요

#include<iostream>
#include<deque>
using namespace std;

int n, maximum;
int board[20][20];
deque<int> dq;

bool move(int dic, int(*tmpboard)[20]){ // top right bot left
	bool change=false;
	switch(dic){
		case 0:
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					if(board[j][i]!=0){
						dq.push_back(board[j][i]);
					}
					board[j][i]=0;
					
				}
				for(int j=0; !dq.empty(); j++){
					board[j][i]=dq.front();
					dq.pop_front();
					if(!dq.empty() && dq.front()==board[j][i]){
						board[j][i]*=2;
						dq.pop_front();
						maximum=max(maximum,board[j][i]);
					}
				}
				if(!change){
					for(int j=0; j<n; j++){
						if(board[j][i]!=tmpboard[j][i]){
							change=true;
							break;
						}
					}
				}
			}
			return change;
			
		case 1:
			for(int j=n-1; j>=0; j--){
				for(int i=n-1; i>=0; i--){
					if(board[j][i]!=0){
						dq.push_back(board[j][i]);
					}
					board[j][i]=0;
					
				}
				for(int i=n-1; !dq.empty(); i--){
					board[j][i]=dq.front();
					dq.pop_front();
					if(!dq.empty() && dq.front()==board[j][i]){
						board[j][i]*=2;
						dq.pop_front();
						maximum=max(maximum,board[j][i]);
					}
				}
				if(!change){
					for(int i=n-1; i>=0; i--){
						if(board[j][i]!=tmpboard[j][i]){
							change=true;
							break;
						}
					}
				}
			}
			return change;
			
		case 2:
			for(int i=n-1; i>=0; i--){
				for(int j=n-1; j>=0; j--){
					if(board[j][i]!=0){
						dq.push_back(board[j][i]);
					}
					board[j][i]=0;
					
				}
				for(int j=n-1; !dq.empty(); j--){
					board[j][i]=dq.front();
					dq.pop_front();
					if(!dq.empty() && dq.front()==board[j][i]){
						board[j][i]*=2;
						dq.pop_front();
						maximum=max(maximum,board[j][i]);
					}
				}
				if(!change){
					for(int j=n-1; j>=0; j--){
						if(board[j][i]!=tmpboard[j][i]){
							change=true;
							break;
						}
					}
				}
			}
			return change;
			
		case 3:
			for(int j=0; j<n; j++){
				for(int i=0; i<n; i++){
					if(board[j][i]!=0){
						dq.push_back(board[j][i]);
					}
					board[j][i]=0;
					
				}
				for(int i=0; !dq.empty(); i++){
					board[j][i]=dq.front();
					dq.pop_front();
					if(!dq.empty() && dq.front()==board[j][i]){
						board[j][i]*=2;
						dq.pop_front();
						maximum=max(maximum,board[j][i]);
					}
				}
				if(!change){
					for(int i=0; i<n; i++){
						if(board[j][i]!=tmpboard[j][i]){
							change=true;
							break;
						}
					}
				}
			}
			return change;
	}
	
	return change;
}

void tbtob(int (*board)[20], int (*tmpboard)[20]){
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			board[i][j]=tmpboard[i][j];
		}
	}
}

void solve(int depth){
	if(depth==5){
		return;
	}
	int tmpboard[20][20];
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			tmpboard[i][j]=board[i][j];
		}
	}
	
	for(int i=0; i<4; i++){
		if(move(i, tmpboard)){
			solve(depth+1);
			tbtob(board,tmpboard);
		}
	}
}

int main(){
	cin>>n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>>board[i][j];
			maximum=max(maximum,board[i][j]);
		}
	}
	solve(0);
	cout<<maximum<<endl;	
}