백준12100 2048 (Easy)

작성일 | In

문제 링크

  • http://icpc.me/12100

사용 알고리즘

  • 브루트 포스

풀이

빡구현 문제이므로 구현해야할 기능들을 먼저 정리해봅시다.

  • 완전탐색 - 재귀호출
  • 상태전이 - 상하좌우 이동
  • 평가 - 현재 상태의 최댓값

상하좌우 이동을 먼저 봅시다. 하나만 잘 구현하면 나머지는 비슷하게 구현할 수 있으므로 하나를 잘 구현하는 것이 관건입니다. 저는 큐를 사용해서 아래와 같은 방식으로 구현했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dw(){
	queue<int> q;
	for(int j=1; j<=n; j++){
		for(int i=n; i>=1; i--){
			if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
		}
		int t = n;
		while(q.size()){
			int now = q.front(); q.pop();
			if(arr[t][j] == 0) arr[t][j] = now;
			else if(arr[t][j] == now) arr[t--][j] *= 2;
			else arr[--t][j] = now;
		}
	}
}

완전탐색 부분은 재귀호출을 이용해 할 것입니다.
bit[5]라는 배열을 만들어서 각 단계마다 어떤 연산을 했는지 기록해둔 다음, 기저조건(연산 5번 완료 이후)에서 bit 배열을 순회하면서 최종 보드판을 만들어 나갑니다.
현재 상태의 최댓값을 구하는 것은 for문을 이용해 간단하게 구현할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int mx;
void solve();

void dfs(int idx){
	if(idx == 5){ solve(); return; }
	for(int i=0; i<4; i++) bit[idx] = i, dfs(idx+1);
}

void solve(){
	memcpy(arr, inp, sizeof arr);
	for(int i=0; i<5; i++){
		if(bit[i] == 0) up(); //위
		if(bit[i] == 1) dw(); //아래
		if(bit[i] == 2) le(); //왼쪽
		if(bit[i] == 3) ri(); //오른쪽
	}
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) mx = max(mx, arr[i][j]);
}

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

int n, mx;
int inp[22][22];
int bit[5];

namespace Solve{
	int arr[22][22];

	void up(){
		queue<int> q;
		for(int j=1; j<=n; j++){
			for(int i=1; i<=n; i++){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = 1;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[t][j] == 0) arr[t][j] = now;
				else if(arr[t][j] == now) arr[t++][j] *= 2;
				else arr[++t][j] = now;
			}
		}
	}

	void dw(){
		queue<int> q;
		for(int j=1; j<=n; j++){
			for(int i=n; i>=1; i--){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = n;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[t][j] == 0) arr[t][j] = now;
				else if(arr[t][j] == now) arr[t--][j] *= 2;
				else arr[--t][j] = now;
			}
		}
	}

	void le(){
		queue<int> q;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = 1;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[i][t] == 0) arr[i][t] = now;
				else if(arr[i][t] == now) arr[i][t++] *= 2;
				else arr[i][++t] = now;
			}
		}
	}

	void ri(){
		queue<int> q;
		for(int i=1; i<=n; i++){
			for(int j=n; j>=1; j--){
				if(arr[i][j]) q.push(arr[i][j]), arr[i][j] = 0;
			}
			int t = n;
			while(q.size()){
				int now = q.front(); q.pop();
				if(arr[i][t] == 0) arr[i][t] = now;
				else if(arr[i][t] == now) arr[i][t--] *= 2;
				else arr[i][--t] = now;
			}
		}
	}
};
using namespace Solve;

void solve();

void dfs(int idx){
	if(idx == 5){
		solve(); return;
	}
	for(int i=0; i<4; i++){
		bit[idx] = i; dfs(idx+1);
	}
}

void solve(){
	memcpy(arr, inp, sizeof arr);
	for(int i=0; i<5; i++){
		if(bit[i] == 0) up();
		if(bit[i] == 1) dw();
		if(bit[i] == 2) le();
		if(bit[i] == 3) ri();
	}

	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) mx = max(mx, arr[i][j]);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> inp[i][j];

	dfs(0);
	cout << mx;
}