[BOJ] 12100번 2048(Easy)

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

 

문제 풀이:

N이 최대 20이고, 5번만 이동시킨다는 조건이 있기 때문에, 완전 탐색으로 풀 수 있다.

 

상하좌우, 4방향으로 숫자들을 민다. -> 5번 움직이므로, 경우의 수는 $4^5$

 

아래의 코드는, 숫자들을 위로 미는 코드이다.

if (dir == 0) { // 위로
		for (int i = 0; i < n; i++) {//y
			int put_idx = -1, cur = -1;
			for (int j = 0; j < n; j++) {//x
				if (arr[j][i] == cur) {
					arr[j][i] = 0;
					arr[put_idx][i] = cur * 2;
					cur = -1;
					res = max(res, arr[put_idx][i]);
				}
				else {
					if (arr[j][i] == 0) continue;
					cur = arr[j][i];
					put_idx++;
					arr[j][i] = 0;
					arr[put_idx][i] = cur;
				}
			}
		}
	}

위에서부터 값을 보면서 아래 값들을 끌어당기는 느낌이다.

현재 값을 cur에 저장하고, 그 밑에 같은 값이 존재하면 합치고, 아니면 다음 칸으로 해당 값을 이동시킨다.

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;


int n,res;
typedef vector<vector<int>> Vv;
Vv move(Vv arr,int dir) {
	if (dir == 0) { // 위로
		for (int i = 0; i < n; i++) {//y
			int put_idx = -1, cur = -1;
			for (int j = 0; j < n; j++) {//x
				if (arr[j][i] == cur) {
					arr[j][i] = 0;
					arr[put_idx][i] = cur * 2;
					cur = -1;
					res = max(res, arr[put_idx][i]);
				}
				else {
					if (arr[j][i] == 0) continue;
					cur = arr[j][i];
					put_idx++;
					arr[j][i] = 0;
					arr[put_idx][i] = cur;
				}
				
			}
		}
	}
	else if (dir == 1) { //아래로
		for (int i = 0; i < n; i++) {//y
			int put_idx = n , cur =-1;
			for (int j = n - 1; j >= 0; j--) {//x
				if (arr[j][i] == cur) {
					arr[j][i] = 0;
					arr[put_idx][i] = cur * 2;
					cur = -1;
					res = max(res, arr[put_idx][i]);
				}
				else {
					if (arr[j][i] == 0) continue;
					cur = arr[j][i];
					put_idx--;
					arr[j][i] = 0;
					arr[put_idx][i] = cur;
				}
			}
		}
	}
	else if (dir == 2) { //왼쪽으로
		for (int i = 0; i < n; i++) {//x
			int put_idx = -1, cur = -1;
			for (int j = 0; j < n; j++) {//y
				if (arr[i][j] == cur) {
					arr[i][j] = 0;
					arr[i][put_idx] = cur * 2;
					cur = -1;
					res = max(res, arr[i][put_idx]);
				}
				else {
					if (arr[i][j] == 0) continue;
					cur = arr[i][j];
					put_idx++;
					arr[i][j] = 0;
					arr[i][put_idx] = cur;
				}
			}
		}
	}
	else { //오른쪽으로
 		for (int i = 0; i < n; i++) {//x
			int put_idx = n , cur = -1;
			for (int j = n - 1; j >= 0; j--) {//y
				if (arr[i][j] == cur) {
					arr[i][j] = 0;
					arr[i][put_idx] = cur * 2;
					cur = -1;
					res = max(res, arr[i][put_idx]);
				}
				else {
					if (arr[i][j] == 0) continue;
					cur = arr[i][j];
					put_idx--;
					arr[i][j] = 0;
					arr[i][put_idx] = cur;
				}
			}
		}
	}
	return arr;
}
void func(Vv arr,int cnt) {
	if (cnt == 5) return;
	for (int i = 0; i < 4; i++) {
		func(move(arr, i), cnt + 1);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	Vv input;
	for (int i = 0; i < n; i++) {
		vector<int> tmp;
		for (int j = 0; j < n; j++) {
			int a;
			cin >> a;
			res = max(res, a);
			tmp.push_back(a);
		}
		input.push_back(tmp);
	}
	func(input, 0);
	cout << res << '\n';
	return 0;
}