[BOJ] 백준 12100번: 2048(Easy)

2048(Easy)

문제

게임의 규칙이 문제의 설명과 같을 때 최대 5번 움직여서 만들수 있는 최대 블록의 값을 구하는 문제이다.

문제 풀이

1. 깊이가 최대 5이고 하나의 상태공간에서 상하좌우 4개의 상태공간으로 전이 가능하다. 

    다음 상태공간을 만드는데 \(O(N^2)\)이 걸리므로, \(O(N^2 4^5)\) 로 해결 가능하다.

2. 각 행(또는 열)에 대해 0이 아닌 블록들을 모은 후 2개씩 묶어서 합치는게 가능하면 합친다. 

    결과를 다시 해당 열에 복사한다.

3. 구현 팁으로는 상, 하 // 좌, 우는 각각 순서만 반대로 넣으면 되고 세로와 가로는 행과 열만 바꾸어 넣으면 된다.

** 구현 실수하기 쉬운 예를 적어 보겠다.

- 상, 하, 좌, 우를 따로 구현 하였는데 규칙이 다르게 구현 되어있음.

- 2 0 2 같이 중간에 0이 끼인 경우를 생각하지 않음.

- dfs 한 후에 다시 복귀할 때 원래 상태로 되돌리지 않음.

- max값을 찾는 시점이 잘못됨. ( 최종 depth가 5일 때 찾아야함 )

- (2 2 4) -> (4 4) 와 같이 이미 결합된 블럭은 한 턴에 다시 결합 하지 않는 규칙을 고려하지 않음

 

소스 코드

	#include <bits/stdc++.h>
	using namespace std;
	int n;
	int mat[20][20];
	// idx = 현재 깊이
	int solve(int idx){
	// 깊이가 5인 경우
	if(idx==5){
	int ret=0;
	// 블록중에 최대 블록을 찾음
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	ret=max(ret, mat[i][j]);
	return ret;
	}
	int ret=0;
	//상하좌우 4방향에 대해서 0좌1우2상3하
	for(int i=0;i<4;i++){
	//현재 상태 공간을 저장
	int temp[20][20];
	for(int j=0;j<n;j++)
	for(int k=0;k<n;k++)
	temp[j][k]=mat[j][k];
	//q행(또는 열)에 대해서 블록을 저장하고 합침
	for(int q=0;q<n;q++){
	//방향이 세로인 경우 행과 열을 뒤집음
	//방향이 1또는 3인경우 순서를 뒤집음
	vector<int> temp;
	for(int p=0;p<n;p++)
	//0이 아닌 원소를 temp 배열에 저장
	if((i<2?mat[q][p]:mat[p][q])!=0)
	temp.push_back(i<2?mat[q][p]:mat[p][q]);
	//뒤집기
	if(i==1||i==3)
	reverse(temp.begin(), temp.end());
	vector<int> perm;
	for(int p=0;p<temp.size();p++)
	//다음 것과 비교해서 같은 경우 2배로 늘려서 perm배열에 저장, 다음 원소는 건너 뜀
	if(p+1<temp.size()&&temp[p]==temp[p+1]){
	perm.push_back(temp[p]*2);
	p++;
	}
	//아닌 경우 그냥 저장
	else
	perm.push_back(temp[p]);
	//빈 공간만큼 0 추가
	for(int p=perm.size();p<n;p++)
	perm.push_back(0);
	//뒤집음
	if(i==1||i==3)
	reverse(perm.begin(), perm.end());
	//다음 상태 공간에 저장
	for(int p=0;p<n;p++)
	(i<2?mat[q][p]:mat[p][q])=perm[p];
	}
	//다음 상태 공간으로 전이
	ret=max(ret, solve(idx+1));
	//원래 상태 공간 복구
	for(int j=0;j<n;j++)
	for(int k=0;k<n;k++)
	mat[j][k]=temp[j][k];
	}
	return ret;
	}
	int main(){
	scanf("%d", &n);
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	scanf("%d", &mat[i][j]);
	printf("%d\n", solve(0));
	return 0;
	}

view raw 12100.cpp hosted with ❤ by GitHub