[12100] 2048(Easy)

풀이

제가 제일 못하는 구현 문제입니다. 그래도 나름 깔끔하게 짜서 결국 통과 받았습니다. 시험장에서 풀었다면 못풀었을 것 같네요..

상하좌우로 기울일 때 배열을 읽는 방향이 중요합니다. 배열이 아래와 같다면

1. 1 2 3
2. 4 5 6
3. 7 8 9

왼쪽으로 기울일 때는 right stack에 3 2 1 순서대로 넣습니다. 1이 top입니다. 그리고 left stack으로 문제의 조건을 만족하면서 옮깁니다. 그리고 이를 다시 배열에 덧씌우는 과정을 진행합니다. stack을 사용하다보니 idx를 적을 때 조금 복잡한 부분이 있습니다.

1. (0,0) (0,1) (0,2)
2. (1,0) (1,1) (1,2)
3. (2,0) (2,1) (2,2)

오른쪽으로 기울일 때는 (0,0),(0,1),(0,2) 값을 순서대로 right에 넣고 문제의 조건을 만족하면서 left stack에 넣습니다. 그리고 left에서 다시 배열에 저장할 때는 저장되는 배열의 좌표를 잘 생각해서 해야합니다.

stack의 이름이 left와 right 인 이유는 제가 노트에 그림을 그려서 해볼 때 왼쪽 오른쪽에 그렸기 때문입니다.

이 문제에서는

1. 완전탐색 dfs를 깔끔하게 짜는 방법
2. 두 개의 배열을 계속해서 사용할 때 깔끔하게 하는 방법

을 공부할 수 있었습니다. PASS를 받고나니 좋은 문제처럼 보이네요 ㅎㅎㅎ.

코드

#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 20
#define LEFT 0
#define RIGHT 1
#define UP 2
#define DOWN 3
int n = 0;
int map[MAX][MAX];
int ans = 0;

void move(stack<pair<int, bool> > &left, stack<int> &right) {
	while (!right.empty()) {
		//오른쪽에서 하나 빼서
		int curr = right.top(); right.pop();
		//왼쪽의 top과 더할 수 있으면 더해서 left에 넣기
		if (!left.empty() && left.top().first == curr && left.top().second == false) {
			pair<int, bool> sum = make_pair(left.top().first + curr, true);
			left.pop();
			left.push(sum);
		}
		else {
			//right에서 left로 하나 옮기기
			left.push(make_pair(curr, false));
		}
	}
}
void tilt(int opt){
	stack<pair<int, bool> > left;
	stack<int> right;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			/*
			1 2 3
			4 5 6
			7 8 9
			*/
			switch (opt) {
			case RIGHT :
				if (map[i][j]) {
					//right : [ 1 2 3(top)
					//left : [ 3 2 1(top)
					right.push(map[i][j]);
					map[i][j] = 0;
				}
				break;
			case LEFT :
				if (map[i][n - 1 - j]) {
					//right : [ 3 2 1(top)
					//left : [ 1 2 3(top)
					right.push(map[i][n - 1 - j]);
					map[i][n - 1 - j] = 0;
				}
				break;
			case UP:
				if (map[n - 1 - j][i]) {
					//right : [ 7 4 1(top)
					//left : [ 1 4 7(top)
					right.push(map[n - 1 - j][i]);
					map[n - 1 - j][i] = 0;
				}
				break;
			case DOWN :
				if (map[j][i]){
					//right : [ 1 4 7(top)
					//left : [ 7 4 1(top)
					right.push(map[j][i]);
					map[j][i] = 0;
				}
				break;
			}
		}
		//이동시키기
		move(left, right);
		//다시 저장하기
		/*
		1 2 3
		4 5 6
		7 8 9
		*/
		int left_size = left.size();
		switch (opt) {
		case LEFT:
			//right : [ 3 2 1(top)
			//left : [ 1 2 3(top)
			if (left_size > 0) {
				for (int j = left_size - 1; j >= 0; j--) {
					map[i][j] = left.top().first; left.pop();
				}
			}
			break;
		case RIGHT:
			//right : [ 1 2 3(top)
			//left : [ 3 2 1(top)
			for (int j = n - left_size; j < n; j++) {
				map[i][j] = left.top().first; left.pop();
			}
			break;
		case UP:
			//right : [ 7 4 1(top)
			//left : [ 1 4 7(top)
			if (left_size > 0) {
				for (int j = left_size-1; j >= 0; j--) {
					map[j][i] = left.top().first; left.pop();
				}
			}
			break;
		case DOWN:
			//right : [ 1 4 7(top)
			//left : [ 7 4 1(top)
			for (int j = n - left_size; j < n; j++) {
				map[j][i] = left.top().first; left.pop();
			}
			break;
		}
	}

}

void findAns(void) {
	int temp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			temp = max(temp, map[i][j]);
		}
	}
	ans = max(ans, temp);
}

void printMap(void) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
}

void dfs(int loop) {
	if (loop == 10) {
		findAns();
		return;
	}
	int temp[MAX][MAX];
	//4방향으로 기울이기
	for (int opt = 0; opt < 4; opt++) { 
		//맵 저장
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				temp[i][j] = map[i][j];
			}
		}
		tilt(opt);
		//printMap();
		dfs(loop + 1);
		//맵 복구
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = temp[i][j];
			}
		}
	}
}

int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	dfs(0);
	printf("%d\n", ans);
	return 0;
}