12100 2048(Easy)

12100 2048(Easy) > 2028KB, 4ms

• 간단한 로직
  • DFS -> 움직임(move) -> DFS
  • 종료조건(cnt==6)에 최종값 갱신
    • 왜 종료조건이 6?
  • 움직임
    • 0이면 다음 숫자 끌어올리고 합치는 동작
    • 0이 아니면 합치는 동작
• 시간 느림 

시간이 느린 이유는 map을 copy하는데 드는 N^2 시간 때문

가로, 세로로 움직이는 건 각각 하나의 함수로 합칠 수 있음

참고 사이트 : https://girlfriend-yerin.tistory.com/99

Baekjoon 12100 2048 (Easy)

 

 

#include <iostream>

#define MAX 20
using namespace std;

int N, map[MAX][MAX], result = 0;
int dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 };

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

int find_max(int map_ori[MAX][MAX]) {
	int rtn = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (rtn < map_ori[i][j]) rtn = map_ori[i][j];

	return rtn;
}

void move(int map_ori[MAX][MAX], int dir) {
	switch (dir) {
	case 0:
		for (int j = 0; j < N; j++) {
			for (int i = 0; i < N; i++) {
				int new_i = i + 1;
				while (new_i < N && map_ori[new_i][j] == 0) new_i++;
				if (new_i == N) break;

				if (map_ori[i][j] == 0) {
					map_ori[i][j] = map_ori[new_i][j];
					map_ori[new_i][j] = 0;
					new_i++;
				}

				while (new_i < N && map_ori[new_i][j] == 0) new_i++;
				if (new_i == N) break;

				if (map_ori[i][j] != 0 && map_ori[new_i][j] == map_ori[i][j]) {
					map_ori[new_i][j] = 0;
					map_ori[i][j] *= 2;
				}
			}
		}
		break;
	case 1:
		for (int j = 0; j < N; j++) {
			for (int i = N - 1; i >= 0; i--) {
				int new_i = i - 1;
				while (new_i >= 0 && map_ori[new_i][j] == 0) new_i--;
				if (new_i == -1) break;

				if (map_ori[i][j] == 0) {
					map_ori[i][j] = map_ori[new_i][j];
					map_ori[new_i][j] = 0;
					new_i--;
				}

				while (new_i >= 0 && map_ori[new_i][j] == 0) new_i--;
				if (new_i == -1) break;

				if (map_ori[i][j] != 0 && map_ori[new_i][j] == map_ori[i][j]) {
					map_ori[new_i][j] = 0;
					map_ori[i][j] *= 2;
				}
			}
		}
		break;
	case 2:
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int new_j = j + 1;
				while (new_j < N && map_ori[i][new_j] == 0) new_j++;
				if (new_j == N) break;

				if (map_ori[i][j] == 0) {
					map_ori[i][j] = map_ori[i][new_j];
					map_ori[i][new_j] = 0;
					new_j++;
				}

				while (new_j < N && map_ori[i][new_j] == 0) new_j++;
				if (new_j == N) break;

				if (map_ori[i][j] != 0 && map_ori[i][new_j] == map_ori[i][j]) {
					map_ori[i][new_j] = 0;
					map_ori[i][j] *= 2;
				}
			}
		}
		break;
	case 3:
		for (int i = 0; i < N; i++) {
			for (int j = N - 1; j >= 0; j--) {
				int new_j = j - 1;
				while (new_j >= 0 && map_ori[i][new_j] == 0) new_j--;
				if (new_j == -1) break;

				if (map_ori[i][j] == 0) {
					map_ori[i][j] = map_ori[i][new_j];
					map_ori[i][new_j] = 0;
					new_j--;
				}

				while (new_j >= 0 && map_ori[i][new_j] == 0) new_j--;
				if (new_j == -1) break;

				if (map_ori[i][j] != 0 && map_ori[i][new_j] == map_ori[i][j]) {
					map_ori[i][new_j] = 0;
					map_ori[i][j] *= 2;
				}
			}
		}
		break;
	}
}

void DFS(int map_ori[MAX][MAX], int dir, int cnt) {
	// stop case
	if (cnt == 6) {
		int findmax = find_max(map_ori);
		if (findmax > result) result = findmax;
		return;
	}

	// map copy
	int map_copy[MAX][MAX];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map_copy[i][j] = map_ori[i][j];

	// move
	move(map_copy, dir);

	// DFS
	for (int i = 0; i < 4; i++)
		DFS(map_copy, i, cnt + 1);

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	input();

	for (int i = 0; i < 4; i++)
		DFS(map, i, 1);

	cout << result;
}