BOJ 12100 2048(Easy) / C++

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

12100번: 2048 (Easy)

백준 온라인 저지 12100번 2048(Easy) 문제입니다.

 

아이디어

문제에 나오는 게임을 해본 경험이 있어서 문제 지문 이해에 어려움이 없었고 array의 상태 저장하여 완전탐색하는 문제의 유형을 코딩테스트, 코딩테스트 모의고사 등에서 겪었던 경험이 있던지라 풀이 자체도 금방 생각이 났고 구현을 했습니다.

주의 할점은 시중에 있는 게임과는 다르게 한쪽으로 이동시에 숫자가 한번만 곂쳐진다는 점입니다. 최초 풀이에는 이 부분을 처리하기 위해 broad와 같은 크기의 bool type의 visited 배열을 이용하여 숫자의 연산이 발생하지 않도록 했는데 평소 구독하고 있던 분의 풀이를 보니 꼭 방문처리가 필요하지 않아 보이고 Queue로 처리하는 부분이 인상 깊어서 비슷한 로직으로 다시 풀이 해보았습니다.

 

#include <iostream>
#include <queue>
#define MAX 20
using namespace std;

enum {
	LEFT = 0,
	RIGHT = 1,
	UP = 2,
	DOWN = 3
};

int N;

int board[MAX][MAX];
int maxBlock;


void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
}


void shiftLeft() {
	queue<int> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			if (board[i][j]) {
				q.push(board[i][j]);
			}

			board[i][j] = 0;
		}

		int pos = 0;

		while (!q.empty()) {

			int data = q.front();
			q.pop();

			if (board[i][pos] == 0) {
				board[i][pos] = data;
			}

			else if (board[i][pos] == data) {
				board[i][pos] *= 2;
				pos++;
			}

			else {
				pos++;
				board[i][pos] = data;
			}

		}

	}
}

void shiftRight() {
	queue<int> q;
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= 0; j--) {
			if (board[i][j]) {
				q.push(board[i][j]);
			}

			board[i][j] = 0;
		}
		int pos = N - 1;

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

			if (board[i][pos] == 0) {
				board[i][pos] = data;
			}

			else if (board[i][pos] == data) {
				board[i][pos] *= 2;
				pos--;
			}

			else {
				pos--;
				board[i][pos] = data;
			}

		}

	}
}

void shiftUp() {
	queue<int> q;
	for (int i = 0; i < N;i++){
		for (int j = 0; j < N;j++){
			if (board[j][i])
				q.push(board[j][i]);

			board[j][i] = 0;
		}

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



			if (board[pos][i] == 0) {
				board[pos][i] = data;
			}

			else if (board[pos][i] == data){
				board[pos][i] *= 2;
				pos++;
			}

			else{
				pos++;
				board[pos][i] = data;
			}
		}
	}
}

void shiftDown() {
	queue<int> q;
	for (int i = 0; i < N;i++){
		for (int j = N - 1; j >=0; j--){
			if (board[j][i]) {
				q.push(board[j][i]);
			}

			board[j][i] = 0;
		}
		int pos = N - 1;

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

			if (board[pos][i] == 0) {
				board[pos][i] = data;
			}

			else if (board[pos][i] == data){
				board[pos][i] *= 2;
				pos--;
			}

			else{
				pos--;
				board[pos][i] = data;
			}
		}
	}
}

void shift(int type){

	if (type == LEFT) {
		shiftLeft();
	}
	
	if (type == RIGHT) {
		shiftRight();
	}

	if (type == UP) {
		shiftUp();
	}

	if (type == DOWN) {
		shiftDown();
	}
}



void DFS(int cnt){

	if (cnt == 5){
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				maxBlock = max(maxBlock, board[i][j]);
			}
		}
		return;
	}


	//현재 보드 상태 저장
	int currentBoard[MAX][MAX];	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			currentBoard[i][j] = board[i][j];
		}
	}



	for (int i = 0; i < 4; i++){
		shift(i);
		DFS(cnt + 1);			

		// 보드를 이전 상태로 되돌림
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = currentBoard[i][j];
			}
		}

	}

}

void solution() {
	DFS(0);
	cout << maxBlock;
}


int main(void){
	input();
	solution();
	return 0;
}