Kang Sang Woo

It is incomplete..

[BOJ12100] 2048 easy

4 분 소요

[BOJ12100] 2048 easy

문제 링크

문제 설명

  • 문제에 대한 설명이 조금 복잡해서 직접 읽어보는걸 추천한다.
  • 한쪽 방향으로 블록을 보내면, 같은 값을 가진 블록들은 합쳐진다. 단 그 방향을 실행할 때 이미 합쳐진 블록들은 합쳐지지 않는다. 다른 방향으로 블록을 보낼 때는 다시 합칠 수 있게된다.
  • 5번을 실행하였을 때, 남아있는 블록 중 가장 큰 값을 출력하는 문제.

코드 리뷰

  • 동,서,남,북으로 블록을 보낼 수 있는데 처음에 재귀로 한번 시행할 때 그 재귀로 들어가서 블록을 움직이고 또 재귀로 들어갈 때 블록을 움직이게 하려고 생각하였다.
  • 하지만 동,서,남,북 4방향중 하나씩 뽑는 행위를 5번 하면 4^5 =1024가지가 나온다. (쉽게 말해 next_permutation stl처럼)
  • 가지수를 미리 만들어두고 블록을 5번 움직여도 시간안에 충분히 답이 나온다.
  • 위의 아이디어를 생각해내고 나면, 그 이후 블록을 움직이는 부분은 시뮬레이션이다.
  • 조건 한 부분에서 실수하여 시간 오바..
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int board[22][22]; //moving board
int field[22][22];
int check[22][22];
char dir[4] = { 'u','d','l','r' };
char pick[5];
int N;
int Max;

void gamestart() {
	memcpy(board, field, sizeof(board));
	for (int i = 0; i < 5; i++) {
		memset(check, 0, sizeof(check));
		if (pick[i] == 'u') {
			for (int m = 0; m < N; m++) {
				for (int n = 0; n < N; n++) {
					if (n == 0) continue;
					if (board[n][m] == 0) continue;
					int idx = n;
					while (1) {
						idx--;
						if (idx >= 0 && board[idx][m] == 0) {
							if (idx == 0) {
								board[idx][m] = board[n][m];
								check[idx][m] = check[n][m];
								board[n][m] = 0;
								check[n][m] = 0;
								break;
							}
						}
						if (idx >= 0 && board[idx][m] != 0) {
							if (board[idx][m] == board[n][m]) {
								if (check[n][m] == 0 && check[idx][m] == 0) {
									board[idx][m] = board[idx][m] + board[n][m];
									board[n][m] = 0;
									check[idx][m] = 1;
									break;
								}
								else {
									if (idx + 1 == n) break;
									else {
										board[idx + 1][m] = board[n][m];
										check[idx + 1][m] = check[n][m];
										board[n][m] = 0;
										check[n][m] = 0;
										break;
									}
								}
							}
							else {
								if (idx + 1 == n) break;
								else {
									board[idx + 1][m] = board[n][m];
									check[idx + 1][m] = check[n][m];
									board[n][m] = 0;
									check[n][m] = 0;
									break;
								}
							}
						}
					}
				}
			}
		}
		if (pick[i] == 'd') {
			for (int m = 0; m < N ; m++) {
				for (int n = N-1; n >=0 ; n--) {
					if (n == N - 1) continue;
					if (board[n][m] == 0) continue;
					int idx = n;
					while (1) {
						idx++;
						if (idx < N && board[idx][m] == 0) {
							if (idx == N - 1) {
								board[idx][m] = board[n][m];
								check[idx][m] = check[n][m];
								board[n][m] = check[n][m] = 0;
								break;
							}
						}
						if (idx < N && board[idx][m] != 0) {
							if (board[idx][m] == board[n][m]) {
								if (check[n][m] == 0 && check[idx][m] == 0) {
									board[idx][m] = board[idx][m] + board[n][m];
									board[n][m] = 0;
									check[idx][m] = 1;
									break;
								}
								else {
									if (idx - 1 == n) break;
									else {
										board[idx - 1][m] = board[n][m];
										check[idx - 1][m] = check[n][m];
										board[n][m] = 0;
										check[n][m] = 0;
										break;
									}
								}
							}
							else {
								if (idx - 1 == n) break;
								else {
									board[idx - 1][m] = board[n][m];
									check[idx - 1][m] = check[n][m];
									board[n][m] = 0;
									check[n][m] = 0;
									break;
								}
							}
						}
					}
				}
			}
		}
		if (pick[i] == 'l') {
			for (int n = 0; n < N; n++) {
				for (int m = 0; m < N; m++) {
					if (m == 0) continue;
					if (board[n][m] == 0) continue;
					int idx = m;
					while (1) {
						idx--;
						if (idx >=0 && board[n][idx] == 0) {
							if (idx == 0) {
								board[n][idx] = board[n][m];
								check[n][idx] = check[n][m];
								board[n][m] = check[n][m] = 0;
								break;
							}
						}
						if(idx>=0 && board[n][idx]!=0) {
							if (board[n][idx] == board[n][m]) {
								if (check[n][m] == 0 && check[n][idx] == 0) {
									board[n][idx] = board[n][idx] + board[n][m];
									board[n][m] = 0;
									check[n][idx] = 1;
									break;
								}
								else {
									if (idx + 1 == m) break;
									else {
										board[n][idx + 1] = board[n][m];
										check[n][idx + 1] = check[n][m];
										board[n][m] = 0;
										check[n][m] = 0;
										break;
									}
								}
							}
							else {
								if (idx + 1 == m) break;
								else {
									board[n][idx + 1] = board[n][m];
									check[n][idx + 1] = check[n][m];
									board[n][m] = 0;
									check[n][m] = 0;
									break;
								}
							}
						}
					}
				}
			}
		}
		if (pick[i] == 'r') {
			for (int n = 0; n < N; n++) {
				for (int m = N - 1; m >= 0; m--) {
					if (m == N - 1) continue;
					if (board[n][m] == 0) continue;
					int idx = m;
					while (1) {
						idx++;
						if (idx < N && board[n][idx] == 0) {
							if (idx == N-1) {
								board[n][idx] = board[n][m];
								check[n][idx] = check[n][m];
								board[n][m] = check[n][m] = 0;
								break;
							}
						}
						if (idx < N  && board[n][idx] != 0) {
							if (board[n][idx] == board[n][m]) {
								if (check[n][m] == 0 && check[n][idx] == 0) {
									board[n][idx] = board[n][idx] + board[n][m];
									board[n][m] = 0;
									check[n][idx] = 1;
									break;
								}
								else {
									if (idx - 1 == m) break;
									else {
										board[n][idx - 1] = board[n][m];
										check[n][idx - 1] = check[n][m];
										board[n][m] = 0;
										check[n][m] = 0;
										break;
									}
								}
							}
							else {
								if (idx - 1 == m) break;
								else {
									board[n][idx - 1] = board[n][m];
									check[n][idx - 1] = check[n][m];
									board[n][m] = 0;
									check[n][m] = 0;
									break;
								}
							}
						}
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			Max = max(Max, board[i][j]);
		}
	}
}

void dfs(int cnt) {
	if (cnt == 5) {
		gamestart();
		return;
	}
	for (int i = 0; i < 4; i++) {
		pick[cnt] = dir[i];
		dfs(cnt + 1);
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < N; m++) {
			cin >> field[n][m];
		}
	}
	dfs(0);
	cout << Max << '\n';
	return 0;
}

댓글남기기

참고