https://www.acmicpc.net/problem/12100
2048 (Easy) 성공
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 11038 | 2534 | 1474 | 21.731% |
문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블럭을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이 때, 같은 값을 갖는 두 블럭이 충돌하면 두 블럭은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블럭은 또 다른 블럭과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블럭이 추가되지만, 이 문제에서 블럭이 추가되는 경우는 없다)
<그림 1> | <그림 2> | <그림 3> |
<그림 1>의 경우에서 위로 블럭을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블럭을 이동시키면 <그림 3>의 상태가 된다.
<그림 4> | <그림 5> | <그림 6> | <그림 7> |
<그림 4>의 상태에서 블럭을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블럭을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블럭을 이동시켜 <그림 7>을 만들 수 있다.
<그림 8> | <그림 9> |
<그림 8>의 상태에서 왼쪽으로 블럭을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
<그림 10> | <그림 11> | <그림 12> | <그림 13> |
<그림 10>에서 위로 블럭을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블럭을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블럭은 또 합쳐질 수 없기 때문이다.
<그림 14> | <그림 15> |
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블럭이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블럭 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블럭의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블럭을 나타낸다. 블럭에 써있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블럭은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블럭을 출력한다.
예제 입력 1
3 2 2 2 4 4 4 8 8 8
예제 출력 1
16
누구나 한 번쯤은 해봤을만한 2048이다. 한창 C++을 학습할때에는 알고리즘에 대한 개념이 부족해서 풀지 못했는데,
최근에 알고리즘 스터디를 하면서 다시 풀어보니 많이 어렵지 않다는 것을 알았다.
4x4라는 제한된 크기 안에서 계산이 이루어지므로 dfs를 사용해서 해결했다.
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 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 | #include<iostream> #include<queue> #include<cstring> using namespace std; int N, MAX = 0; int map_[20][20]; void push_func(int num); void dfs(int count); void print(int temp[20][20]); int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &map_[i][j]); } } dfs(0); printf("%d", MAX); return 0; } void push_func(int num) { queue<int> temp; int temp1; int map_count = 0; switch(num) { case 0: // left for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (map_[i][j] != 0) { temp.push(map_[i][j]); map_[i][j] = 0; } } map_count = 0; while (temp.empty() == false) { temp1 = temp.front(); temp.pop(); if (map_[i][map_count] == 0) { map_[i][map_count] = temp1; } else if (map_[i][map_count] == temp1) { map_[i][map_count] = map_[i][map_count] + map_[i][map_count]; map_count++; } else { map_[i][++map_count] = temp1; } } } break; case 1: // right for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (map_[i][N - 1 - j] != 0) { temp.push(map_[i][N - 1 - j]); map_[i][N - 1 - j] = 0; } } map_count = 0; while (temp.empty() == false) { temp1 = temp.front(); temp.pop(); if (map_[i][N - 1 - map_count] == 0) { map_[i][N - 1 - map_count] = temp1; } else if (map_[i][N - 1 - map_count] == temp1) { map_[i][N - 1 - map_count] *= 2; map_count++; } else { map_[i][N - 1 - ++map_count] = temp1; } } } break; case 2: // up for (int j = 0; j < N; j++) { for (int i = 0; i < N; i++) { if (map_[i][j] != 0) { temp.push(map_[i][j]); map_[i][j] = 0; } } map_count = 0; while (temp.empty() == false) { temp1 = temp.front(); temp.pop(); if (map_[map_count][j] == 0) { map_[map_count][j] = temp1; } else if (map_[map_count][j] == temp1) { map_[map_count][j] *= 2; map_count++; } else { map_[++map_count][j] = temp1; } } } break; case 3: // down for (int j = 0; j < N; j++) { for (int i = 0; i < N; i++) { if (map_[N - 1 - i][j] != 0) { temp.push(map_[N - 1 - i][j]); map_[N - 1 - i][j] = 0; } } map_count = 0; while (temp.empty() == false) { temp1 = temp.front(); temp.pop(); if (map_[N - 1 - map_count][j] == 0) { map_[N - 1 - map_count][j] = temp1; } else if (map_[N - 1 - map_count][j] == temp1) { map_[N - 1 - map_count][j] *= 2; map_count++; } else { map_[N - 1 - ++map_count][j] = temp1; } } } break; default: break; } } void dfs(int count) { if (count == 5) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (MAX < map_[i][j]) MAX = map_[i][j]; } } return; } else { int temp_map[20][20]; memcpy(temp_map, map_, 400 * sizeof(int)); for (int i = 0; i < 4; i++) { push_func(i); dfs(count + 1); memcpy(map_, temp_map, 400 * sizeof(int)); } } } void print(int temp[20][20]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("%d ", temp[i][j]); } printf("\n"); } } | cs |
'Programming > BOJ Solutions' 카테고리의 다른 글
[백준 13458번] 시험 감독 (0) | 2018.06.19 |
---|---|
[백준 1260번] DFS와 BFS (0) | 2018.06.19 |
[백준 1194번] 달이 차오른다, 가자 (0) | 2018.06.19 |
[백준 1018번] 체스판 다시 칠하기 (0) | 2018.06.19 |
[백준 1003번] 피보나치 함수 (0) | 2018.06.19 |