JUST WRITE IT. HomeArchivesTagsCategories
백준 12100번 2048(Easy)
|AlgorithmBOJ|

#12100. 2048(Easy)

문제링크

Problem

  • N x N 크기의 보드판
  • 한 번의 이동 : 보드판에 있는 모든 블록 상하좌우 중 한 방향으로 쭉 이동
    단순히 한 칸이 아닌 해당 방향 이동할 수 있는 곳 끝까지
  • 같은 값을 가진 블록이 충돌하면 하나로 합쳐짐
    (한 번 합쳐지면 다시 합칠 수 없음 → 한 번 이동할 때 연속으로 합쳐질 수 없음 2개 → 1개인 경우만 존재)
    블록이 합쳐지면 해당 블록의 숫자를 더한 값이 된다.

Goal: 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값 구하기

  • 입력

    N: ~20
    0: 빈칸
    2^i(i= 1, 2…10): 블록 // 적어도 하나 주어짐

Solution

  • 최대 5번 이동이니 한 번 이동하면서 최대 블록 값을 갱신해주어야 한다.
    (꼭 안그래도 되겠지만)
  1. 5번 이동하는 조합을 구한다.
  2. 그 이동에 맞게 블록을 이동시킨다.
  • 해당 번째의 방향을 저장할 배열을 이용해 5개의 방향을 저장해놓고, 모두 저장했을 때 보드판을 움직이도록 한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void dfs(int idx) {
    	if (idx == 5) { // 방향 5개가 저장되었을 때
    		for (int i = 0; i < n; ++i) { // 입력값인 temp를 board로 옮기고 작업을 수행한다.
    			for (int j = 0; j < n; ++j) {
    				board[i][j] = temp[i][j];
    			}
    		}
    		for (int i = 0; i < 5; ++i) { 
    			moveBlock(해당 방향);
    		}
    		return;
    	}
    	for (int i = 0; i < 4; ++i) {
    		direction[idx] = i;
    		dfs(idx+1);
    	}
    }
  • moveBlock() 블럭 이동

움직이는 방향이 좌우면 한 행의 열이 바뀌면서 board위의 블럭들이 바뀐다.
이때 좌로 이동하면 오른쪽부터 탐색, 우로 이동하면 왼쪽부터 탐색해야 한다.

움직이는 방향이 상하일 때도 위와 같은 방식이다. 이를 잘 구분해주어 update할 때 행, 열의 인덱스를 반영한다.

  • update() 아래 코드는 좌우로 이동할 때 블럭들을 갱신하는 함수다.
    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
    void updateCol(int i, int j, queue<int> &zero) {
    	if (board[i][j] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[i][value_idx] *= 2;
    		answer = max(answer, board[i][value_idx]);
    		board[i][j] = 0;
    		zero.push(j);
    	}
    	else if (board[i][j] != 0) {
    		value_idx = j;
    		value = board[i][j];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[i][j] = 0;
    			board[i][zero_idx] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    3가지 경우를 확인하고 각 작업을 수행한다.
  1. 블럭이 없는 빈 곳: queue에 해당 위치를 넣어준다. (블럭을 옮길 때 쓰임)
  2. 합칠 대상이 되는 블럭: 이전에 저장해놓은 블럭 값과 같으면 합칠 수 있다.
    이전에 저장해놓은 블럭의 값을 2배로 하고 합칠 대상이 되는 블럭은 0으로 바꾼뒤 이 위치를 queue에 넣어준다.
  3. 합쳐질 가능성이 있는 블럭: 이 값은 나중에 합쳐질 수 있으므로 해당 값과 위치를 저장해 놓는다.
    단, queue가 비어있지 않다면 이 블럭의 위치를 옮겨주어야 하기에 queue에서 pop한 0의 위치로 해당 블럭 값을 넣어준다.
    이렇게 되면 바뀌기 전 블럭은 0이 되고 이 위치를 다시 queue에 넣어주어야 한다.
    마지막으로 위치가 바뀐 지점을 갱신해주면 된다.

1 Try

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <queue>
#include <algorithm>
#define MAX 20
using namespace std;
int n, value, value_idx, zero_idx, answer = 2;
int board[MAX][MAX];
int temp[MAX][MAX];
int direction[5]; // 방향 조합 0:상, 1:하, 2:좌, 3:우
void updateCol(int i, int j, queue<int> &zero) {
	if (board[i][j] == 0) { // 0의 위치
		zero.push(j);
	}
	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
		board[i][value_idx] *= 2;
		answer = max(answer, board[i][value_idx]);
		board[i][j] = 0;
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[i][zero_idx] = value;
		}
		zero.push(j);
	}
	else if (board[i][j] != 0) {
		value_idx = j;
		value = board[i][j];
		answer = max(answer, value);
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[i][j] = 0;
			board[i][zero_idx] = value;
			zero.push(j);
		}
	}
}
void updateRow(int i, int j, queue<int> &zero) {
	if (board[j][i] == 0) { // 0의 위치
		zero.push(j);
	}
	else if (board[j][i] != 0 && board[j][i] == value) { // 블럭 값이 같을 때
		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
		board[value_idx][i] *= 2;
		answer = max(answer, board[value_idx][i]);
		board[j][i] = 0;
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[zero_idx][i] = value;
		}
		zero.push(j);
	}
	else if (board[j][i] != 0) {
		value_idx = j;
		value = board[j][i];
		answer = max(answer, value);
		if (!zero.empty()) {
			zero_idx = zero.front();
			zero.pop();
			board[j][i] = 0;
			board[zero_idx][i] = value;
			zero.push(j);
		}
	}
}
void moveBlock(int move) {
	for (int i = 0; i < n; ++i) {
		queue<int> zero;
		value = 0; value_idx = 0; zero_idx = 0;
		if (move % 2 == 0) {
			for (int j = 0; j < n; ++j) {
				if (move == 0) {
					updateRow(i, j, zero);
				}
				else {
					updateCol(i, j, zero);
				}
			}
		}
		else {
			for (int j = n-1; j >= 0; --j) {
				if (move == 1) {
					updateRow(i, j, zero);
				}
				else {
					updateCol(i, j, zero);
				}
			}
		}
	}
}
void dfs(int idx) {
	if (idx == 5) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				board[i][j] = temp[i][j];
			}
		}
		for (int i = 0; i < 5; ++i) {
			moveBlock(direction[i]);
		}
		return;
	}
	for (int i = 0; i < 4; ++i) {
		direction[idx] = i;
		dfs(idx+1);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &temp[i][j]);
		}
	}
	dfs(0);
	printf("%d\n", answer);
	return 0;
}

위의 코드가 틀린 Test case

7
2 2 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 2 2 0 2 2 2 
2 2 2 2 2 2 0
2 2 2 2 2 2 0
-> 32 // output

디버깅용 코드를 보면 알겠지만 방향을 3(오른쪽)으로 했을 때 board의 블럭들을 확인해보니
실제로 잘 합쳐지지 않았던 것이다. (solution에는 정답 코드를 반영)

  • 위 코드의 빨간 줄을 없애주었다. 합쳐지면 0이 있는 곳을 찾아 넣는 작업을 하면 안되기 때문이다. 이 블럭은 합쳐졌고, 이 위치는 0으로 채우고 이 인덱스를 queue에 넣어주기만 하면 된다.
  • queue가 비어있지 않다면 해당 지점에 블럭을 놓는 작업이 있는데
    이때, value_idx = zero_idx 를 추가해주어야 해당 블럭의 바뀐 위치도 알 수 있다.
    이를 추가하지 않으면 바뀌기 전 위치가 남아있어 합쳐지지 않는다.

Debug

  • 코드 보기
    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
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    #include <cstdio>
    #include <queue>
    #include <algorithm>
    #define MAX 20
    using namespace std;
    int n, value, value_idx, zero_idx, answer = 2;
    int board[MAX][MAX];
    int temp[MAX][MAX];
    int direction[5]; // 방향 조합 0:상, 1:하, 2:좌, 3:우
    void updateCol(int i, int j, queue<int> &zero) {
    	if (board[i][j] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[i][value_idx] *= 2;
    		answer = max(answer, board[i][value_idx]);
    		board[i][j] = 0;
    		zero.push(j);
    	}
    	else if (board[i][j] != 0) {
    		value_idx = j;
    		value = board[i][j];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[i][j] = 0;
    			board[i][zero_idx] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    	//printf("%d-%d번재: \n", i, j);
    	//for (int i = 0; i < n; ++i) {
    	//	for (int j = 0; j < n; ++j) {
    	//		printf("%d ", board[i][j]);
    	//	}
    	//	printf("\n");
    	//}
    }
    void updateRow(int i, int j, queue<int> &zero) {
    	if (board[j][i] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[j][i] != 0 && board[j][i] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[value_idx][i] *= 2;
    		answer = max(answer, board[value_idx][i]);
    		board[j][i] = 0;
    		zero.push(j);
    	}
    	else if (board[j][i] != 0) {
    		value_idx = j;
    		value = board[j][i];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[j][i] = 0;
    			board[zero_idx][i] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    void moveBlock(int move) {
    	for (int i = 0; i < n; ++i) {
    		queue<int> zero;
    		value = 0; value_idx = 0; zero_idx = 0;
    		if (move % 2 == 0) {
    			for (int j = 0; j < n; ++j) {
    				if (move == 0) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    		else {
    			for (int j = n-1; j >= 0; --j) {
    				if (move == 1) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    	}
    }
    void dfs(int idx) {
    	if (idx == 5) {
    		for (int i = 0; i < n; ++i) {
    			for (int j = 0; j < n; ++j) {
    				board[i][j] = temp[i][j];
    			}
    		}
    		for (int i = 0; i < 5; ++i) {
    			moveBlock(direction[i]);
    		}
    		return;
    	}
    	for (int i = 0; i < 4; ++i) {
    		direction[idx] = i;
    		dfs(idx+1);
    	}
    }
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < n; ++j) {
    			scanf("%d", &temp[i][j]);
    		}
    	}
    	//dfs(0);
    	direction[0] = 3; 
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < n; ++j) {
    			board[i][j] = temp[i][j];
    		}
    	}
    	moveBlock(direction[0])
    	printf("\n");
    	printf("%d\n", answer);
    	return 0;
    }

    2 Try

    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
    108
    109
    110
    111
    112
    113
    #include <cstdio>
    #include <queue>
    #include <algorithm>
    #define MAX 20
    using namespace std;
    int n, value, value_idx, zero_idx, answer = 2;
    int board[MAX][MAX];
    int temp[MAX][MAX];
    int direction[5]; // 방향 조합 0:상, 1:하, 2:좌, 3:우
    void updateCol(int i, int j, queue<int> &zero) {
    	if (board[i][j] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[i][j] != 0 && board[i][j] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[i][value_idx] *= 2;
    		answer = max(answer, board[i][value_idx]);
    		board[i][j] = 0;
    		zero.push(j);
    	}
    	else if (board[i][j] != 0) {
    		value_idx = j;
    		value = board[i][j];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[i][j] = 0;
    			board[i][zero_idx] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    void updateRow(int i, int j, queue<int> &zero) {
    	if (board[j][i] == 0) { // 0의 위치
    		zero.push(j);
    	}
    	else if (board[j][i] != 0 && board[j][i] == value) { // 블럭 값이 같을 때
    		value = 0; // 한 번에 한 번만 합치도록 0으로 초기화
    		board[value_idx][i] *= 2;
    		answer = max(answer, board[value_idx][i]);
    		board[j][i] = 0;
    		zero.push(j);
    	}
    	else if (board[j][i] != 0) {
    		value_idx = j;
    		value = board[j][i];
    		answer = max(answer, value);
    		if (!zero.empty()) {
    			zero_idx = zero.front();
    			zero.pop();
    			board[j][i] = 0;
    			board[zero_idx][i] = value;
    			zero.push(j);
    			value_idx = zero_idx; // 변경
    		}
    	}
    }
    void moveBlock(int move) {
    	for (int i = 0; i < n; ++i) {
    		queue<int> zero;
    		value = 0; value_idx = 0; zero_idx = 0;
    		if (move % 2 == 0) {
    			for (int j = 0; j < n; ++j) {
    				if (move == 0) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    		else {
    			for (int j = n-1; j >= 0; --j) {
    				if (move == 1) {
    					updateRow(i, j, zero);
    				}
    				else {
    					updateCol(i, j, zero);
    				}
    			}
    		}
    	}
    }
    void dfs(int idx) {
    	if (idx == 5) {
    		for (int i = 0; i < n; ++i) {
    			for (int j = 0; j < n; ++j) {
    				board[i][j] = temp[i][j];
    			}
    		}
    		for (int i = 0; i < 5; ++i) {
    			moveBlock(direction[i]);
    		}
    		return;
    	}
    	for (int i = 0; i < 4; ++i) {
    		direction[idx] = i;
    		dfs(idx+1);
    	}
    }
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < n; ++j) {
    			scanf("%d", &temp[i][j]);
    		}
    	}
    	dfs(0);
    	printf("%d\n", answer);
    	return 0;
    }
Algorithm