[백준] 12100. 2048(Easy)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

#include<bits/stdc++.h>

using namespace std;

int n, x;
vector<int>answer;
int ans = -1;
void add(vector<vector<int>>& mp,int d) {
	switch (d) {
	case 0:
		for (int j = 0; j < n; j++) {
			for (int i = 0; i < n - 1; i++) {
				if (mp[i][j] == -1)continue;
				for (int k = i+1; k < n; k++) {
					if (mp[k][j] != -1) {
						if (mp[i][j] == mp[k][j]) {
							mp[i][j] *= 2;
							mp[k][j] = -1;
						}
						break;
					}
				}
			}
		}
		break;
	case 1:
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j > 0; j--) {
				if (mp[i][j] == -1)continue;
				for (int k = j - 1; k >= 0; k--) {
					if (mp[i][k] != -1) {
						if (mp[i][j] == mp[i][k]) {
							mp[i][j] *= 2;
							mp[i][k] = -1;
						}
						break;
					}
				}
			}
		}
		break;
		
	case 2:
		for (int j = 0; j < n; j++) {
			for (int i = n - 1; i > 0; i--) {
				if (mp[i][j] == -1)continue;
				for (int k = i - 1; k >= 0; k--) {
					if (mp[k][j] != -1) {
						if (mp[i][j] == mp[k][j]) {
							mp[i][j] *= 2;
							mp[k][j] = -1;
						}
						break;
					}
				}
			}
		}
		break;
	case 3:
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n - 1; j++) {
				if (mp[i][j] == -1)continue;
				for (int k = j + 1; k < n; k++) {
					if (mp[i][k] != -1) {
						if (mp[i][j] == mp[i][k]) {
							mp[i][j] *= 2;
							mp[i][k] = -1;
						}
						break;
					}
				}
			}
		}
		break;
	}
}
void push(vector<vector<int>>& mp, int d) {
	switch (d) {
	case 0:
		for (int j = 0; j < n; j++) {
			for (int i = 1; i < n; i++) {
				for (int k = 0; k < i; k++) {
					if (mp[k][j] == -1) {
						mp[k][j] = mp[i][j];
						mp[i][j] = -1;
						break;
					}
				}
			}
		}
		break;
	case 1:
		for (int i = 0; i < n; i++) {
			for (int j = n - 2; j >=0 ; j--) {
				for (int k = n-1; k > j; k--) {
					if (mp[i][k] == -1) {
						mp[i][k] = mp[i][j];
						mp[i][j] = -1;
						break;
					}
				}
			}
		}
		break;
	case 2:
		for (int j = 0; j < n; j++) {
			for (int i = n - 2; i >= 0; i--) {
				for (int k = n - 1; k > i; k--) {
					if (mp[k][j] == -1) {
						mp[k][j] = mp[i][j];
						mp[i][j] = -1;
						break;
					}
				}
			}
		}
		break;
	case 3:
		for (int i = 0; i < n; i++) {
			for (int j = 1; j < n; j++) {
				for (int k = 0; k < j; k++) {
					if (mp[i][k] == -1) {
						mp[i][k] = mp[i][j];
						mp[i][j] = -1;
						break;
					}
				}
			}
		}
		break;
	}
}
void bt(int k,vector<vector<int>>mp ) {
	int M = -1;
	if (k == 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				M = max(M, mp[i][j]);
			}
		}
		ans = max(ans, M);
		return;
	}
	for (int i = 0; i < 4; i++) {
		vector<vector<int>>temp;
		temp = mp;
		add(temp,i);
		push(temp,i);
		bt(k + 1, temp);
	}
}
int main() {
	 ios_base::sync_with_stdio;
	 cin.tie(NULL);
	 cout.tie(NULL);
	 vector<vector<int>>mp;
	 cin >> n;
	 for (int i = 0; i < n; i++) {
		 vector<int>vt;
		 mp.push_back(vt);
		 for (int j = 0; j < n; j++) {
			 mp[i].push_back(-1);
		 }
	 }
	
	
	 for (int i = 0; i < n; i++) {
		 for (int j = 0; j < n; j++) {
			 cin >> x;
			 if (x == 0)mp[i][j] = -1;
			 else
			 mp[i][j] = x;
		 }
	 }
	 bt(0,mp);
	 cout << ans;

}

골드2 백트래킹, 구현, 시뮬레이션 문제다.

(장황하게 푼듯한..)

실제 NxN칸을 만들고, 수를 합쳐주는 add함수와 밀어주는 push함수를 만들었다.

사실 나머지 백트래킹은 결국 브루트포스 방식과 동일하게 깊이 5로 모든 경우를 탐색하게 만들었다.

 

중간에 등호 = 하나 오타내서 찾느라 고생..