백준 12100 ( Easy)

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

12100번: 2048 (Easy)

 

문제 풀이 방법

1. 오른쪽, 왼쪽, 위, 아래 방향으로 map 배열의 요소를 이동시켜주는 함수

2. 위에서 만든 함수의 각 동작을 DFS로 완전탐색 시키며 중복순열을 이용한다. ( 위, 위, 위, 위, 위 -> 위 위 위 위 아래 -> 위 위 위 위 왼 -> 위 위 위 위 오 )

3. max 회전 횟수인 5번일때 map 배열을 최대값 추출 후 최대값 갱신

 

위의 문제는 사실 풀이는 쉽지만 오른쪽, 위, 아래, 왼쪽 방향을 재각각 움직여 주는 노가다가 필요하기 때문에 Queue를 이용하여 0이 아닌 값들만 push 후 기존에 map의 값은 0으로 초기화 한다. 그 뒤 큐에 front에 위치한 정보를 가져 오면서 map배열의 가장자리부터 채워 넣는다. 이때 중요한것은 바뀌기 전 map 배열의 정보를 백업한 뒤 재귀가 끝난 뒤 다시 바뀌기 전의 map 배열 상태로 돌려놓는 작업을 해야한다.

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int map[20][20];
int maxx = 0;
int n;

int getMax(){
	int ma = 0;

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (ma < map[i][j]) ma = map[i][j];
		}
	}
	return ma;
}

void move_map(int dir){
	queue<int> qu;
	// up
	if (dir == 1){
		for (int i = 0; i < n; ++i){
			int idx = 0;
			for (int j = 0; j < n; ++j){
				if (map[j][i] > 0) {
					qu.push(map[j][i]);
					map[j][i] = 0;
				}
			}
			while (!qu.empty()){
				if (map[idx][i] == 0){
					map[idx][i] = qu.front();
					qu.pop();
				}
				else{
					if (map[idx][i] == qu.front()){
						map[idx][i] *= 2;
						++idx;
						qu.pop();
					}
					else {
						idx++;
						map[idx][i] = qu.front();
						qu.pop();
					}
				}
			}
		}
	}

	// down
	if (dir == 2){
		for (int i = 0; i < n; ++i){
			int idx = n - 1;
			for (int j = n - 1; j >= 0; --j){
				if (map[j][i] > 0) {
					qu.push(map[j][i]);
					map[j][i] = 0;
				}
			}
			while (!qu.empty()){
				if (map[idx][i] == 0){
					map[idx][i] = qu.front();
					qu.pop();
				}
				else{
					if (map[idx][i] == qu.front()){
						map[idx][i] *= 2;
						--idx;
						qu.pop();
					}
					else {
						--idx;
						map[idx][i] = qu.front();
						qu.pop();
					}
				}
			}
		}
	}

	// left
	if (dir == 3){
		for (int i = 0; i < n; ++i){
			int idx = 0;
			for (int j = 0; j < n; ++j){
				if (map[i][j] > 0) {
					qu.push(map[i][j]);
					map[i][j] = 0;
				}
			}
			while (!qu.empty()){
				if (map[i][idx] == 0){
					map[i][idx] = qu.front();
					qu.pop();
				}
				else{
					if (map[i][idx] == qu.front()){
						map[i][idx] *= 2;
						++idx;
						qu.pop();
					}
					else {
						++idx;
						map[i][idx] = qu.front();
						qu.pop();
					}
				}
			}
		}
	}

	// right
	if (dir == 4){
		for (int i = 0; i < n; ++i){
			int idx = n - 1;
			for (int j = n - 1; j >= 0; --j){
				if (map[i][j] > 0) {
					qu.push(map[i][j]);
					map[i][j] = 0;
				}
			}
			while (!qu.empty()){
				if (map[i][idx] == 0){
					map[i][idx] = qu.front();
					qu.pop();
				}
				else{
					if (map[i][idx] == qu.front()){
						map[i][idx] *= 2;
						--idx;
						qu.pop();
					}
					else {
						--idx;
						map[i][idx] = qu.front();
						qu.pop();
					}
				}
			}
		}
	}
}

void dfs(int level){
	int cpMap[20][20];
	memcpy(cpMap, map, 4 * 20 * 20);

	if (level == 5){
		int tmp = getMax();
		if (maxx < tmp) maxx = tmp;
		return;
	}

	for (int i = 1; i <= 4; ++i){
		move_map(i);
		dfs(level + 1);
		memcpy(map, cpMap, 4 * 20 * 20);
	}

}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			cin >> map[i][j];
		}
	}
	dfs(0);
	printf("%d", maxx);


}