(c++)백준 12100번: 2048 (Easy)

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

[풀이]

dfs 중복순열을 구하는 방법을 이용하여 5번 이동시키는 모든 경우에 대해 얻을 수 있는 가장 큰 블록을 구하였다.

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int Board[20][20];
int c_Board[20][20];
int Order[5];
const int dx[] = { -1,1,0,0 };//위,아래
const int dy[] = { 0,0,-1,1 };//왼,오
int Max = -1;

void copyBoard() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			c_Board[i][j] = Board[i][j];
		}
	}
}

void MoveUp() {
	//1행부터
	for (int x = 1; x < N; x++) {
		for (int y = 0; y < N; y++) {
			if (c_Board[x][y] == 0)
				continue;
			//바로 윗칸이 빈칸이면
			if (c_Board[x - 1][y] == 0) {
				int nx = x + dx[0];
				//빈칸 아닐때까지
				while (c_Board[nx][y] == 0) {
					nx += dx[0];
					if (nx < 0)
						break;
				}
				nx -= dx[0];
				c_Board[nx][y] = c_Board[x][y];
				c_Board[x][y] = 0;
			}
		}
	}
}


void MoveDown() {
	//N-2행부터
	for (int x = N - 2; x >= 0; x--) {
		for (int y = 0; y < N; y++) {
			if (c_Board[x][y] == 0)
				continue;
			//바로 아래칸이 빈칸이면
			if (c_Board[x + 1][y] == 0) {
				int nx = x + dx[1];
				//빈칸 아닐 때까지
				while (c_Board[nx][y] == 0) {
					nx += dx[1];
					if (nx >= N)
						break;
				}
				nx -= dx[1];
				c_Board[nx][y] = c_Board[x][y];
				c_Board[x][y] = 0;
			}
		}
	}
}

void MoveLeft() {
	//1열부터
	for (int y = 1; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (c_Board[x][y] == 0)
				continue;
			//바로 왼쪽칸이 빈칸이면
			if (c_Board[x][y - 1] == 0) {
				int ny = y + dy[2];
				//빈칸 아닐 때까지
				while (c_Board[x][ny] == 0) {
					ny += dy[2];
					if (ny < 0)
						break;
				}
				ny -= dy[2];
				c_Board[x][ny] = c_Board[x][y];
				c_Board[x][y] = 0;
			}
		}
	}
}

void MoveRight() {
	//N-2열부터
	for (int y = N - 2; y >= 0; y--) {
		for (int x = 0; x < N; x++) {
			if (c_Board[x][y] == 0)
				continue;
			//바로 오른쪽칸이 빈칸이면
			if (c_Board[x][y + 1] == 0) {
				int ny = y + dy[3];
				//빈칸 아닐 때까지
				while (c_Board[x][ny] == 0) {
					ny += dy[3];
					if (ny >= N)
						break;
				}
				ny -= dy[3];
				c_Board[x][ny] = c_Board[x][y];
				c_Board[x][y] = 0;
			}
		}
	}
}

void MergeUp() {
	//아래칸과 같은 블록 있으면 합치기
	for (int x = 0; x < N - 1; x++) {
		for (int y = 0; y < N; y++) {
			if (c_Board[x][y] == 0)
				continue;
			if (c_Board[x][y] == c_Board[x + 1][y]) {
				c_Board[x][y] = 2 * c_Board[x][y];
				c_Board[x + 1][y] = 0;
				Max = max(Max, c_Board[x][y]);
			}
		}
	}
}

void MergeDown() {
	//윗칸과 같은 블록 있으면 합치기
	for (int x = N - 1; x > 0; x--) {
		for (int y = 0; y < N; y++) {
			if (c_Board[x][y] == 0)
				continue;
			if (c_Board[x][y] == c_Board[x - 1][y]) {
				c_Board[x][y] = 2 * c_Board[x][y];
				c_Board[x - 1][y] = 0;
				Max = max(Max, c_Board[x][y]);
			}
		}
	}
}

void MergeLeft() {
	//0열부터
	for (int y = 0; y < N - 1; y++) {
		for (int x = 0; x < N; x++) {
			if (c_Board[x][y] == 0)
				continue;
			//오른쪽 칸과 블록이 같으면
			if (c_Board[x][y] == c_Board[x][y + 1]) {
				c_Board[x][y] = 2 * c_Board[x][y];
				c_Board[x][y + 1] = 0;
				Max = max(Max, c_Board[x][y]);
			}
		}
	}
}

void MergeRight() {
	//N-1열부터
	for (int y = N - 1; y > 0; y--) {
		for (int x = 0; x < N; x++) {
			if(c_Board[x][y] == 0)
				continue;
			//왼쪽칸과 블록이 같으면
			if (c_Board[x][y] == c_Board[x][y - 1]) {
				c_Board[x][y] = 2 * c_Board[x][y];
				c_Board[x][y - 1] = 0;
				Max = max(Max, c_Board[x][y]);
			}
		}
	}
}

void Move() {
	copyBoard();
	for (int i = 0; i < 5; i++) {
		int d = Order[i];
		//위로
		if (d == 0) {
			MoveUp();
			MergeUp();
			MoveUp();
		}
		//아래로
		else if (d == 1) {
			MoveDown();
			MergeDown();
			MoveDown();
		}
		//왼쪽으로
		else if (d == 2) {
			MoveLeft();
			MergeLeft();
			MoveLeft();
		}
		//오른쪽으로
		else if (d == 3) {
			MoveRight();
			MergeRight();
			MoveRight();
		}
	}
}

//중복 순열 구하기
void getOrder(int cnt) {
	if (cnt == 5) {
		Move();
		return;
	}
	for (int i = 0; i < 4; i++) {
		Order[cnt] = i;
		getOrder(cnt + 1);
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Board[i][j];
			Max = max(Max, Board[i][j]);
		}
	}
	getOrder(0);
	/*
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << Board[i][j] << ' ';
		}
		cout << '\n';
	}*/
	cout << Max << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}