https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
[ 문제풀이 ]
구현 방법은 그렇게 어렵지는 않았으나 생각보다 까다로운 문제였습니다.
먼저 합쳐야 하는 숫자들을 판단해야 했습니다. 합쳐지는 숫자들은 한쪽 방향으로 움직였을 때 충돌하는 숫자와 같은 값을 가져야 했고, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다는 조건이 있었습니다.
이러한 조건을 만족하기 위해서 방향을 정해 움직였을 때 어떠한 결과가 나오는지 구현할 수 있는 함수를 먼저 만들었습니다.
위와 같은 상황에서 위로 블록을 이동시키면 다음과 같은 결과가 나옵니다.
4와 4는 같은 숫자이지만 합쳐지지 않았는데, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다는 조건 때문입니다.
그렇다면 이를 어떤 식으로 구현해야 할까요?
블록을 움직일 방향이 왼쪽일 때를 예로 들면 왼쪽에 있는 블록부터 합쳐지기 때문에 왼쪽부터 오른쪽으로 배열을 탐색하면서 오른쪽에 있는 블록이 나와 같은 값을 가지고 있는지 체크하고, 같다면 합치고, 같지 않다면 그대로 두는 방법으로 구현했습니다.
그리고 합치는 과정을 모두 거친 후 모든 블록들을 왼쪽으로 밀어야 했는데 배열을 왼쪽부터 오른쪽으로 탐색하며 0이 아닌 숫자를 만나면 제일 왼쪽 칸부터 차곡차곡 쌓아주는 방식으로 구현했습니다.
하지만 여기서 문제가 발생했는데, 4방향을 모두 구현하기 위해서는 함수가 매우 길어질 것이라고 생각했습니다.
함수가 길어지면 실수를 할 수도 있고, 디버깅을 할 때도 쉽지 않을 것이라고 생각이 들어서 배열을 90도씩 돌리면서 한쪽으로 밀면 네 방향으로 움직일 수 있을 것이라고 생각했습니다.
마지막으로 재귀 함수를 통해서 최댓값을 구했습니다.
백트래킹을 위해서 temp라는 배열을 만들고 temp배열에 arr를 저장하고 재귀함수를 빠져나올 때 arr에 다시 temp를 저장하는 방식으로 구현했습니다.
만약 5번을 다 움직였다면 arr배열을 모두 탐색하며 가장 큰 숫자를 ans에 넣었고, ans를 출력했습니다.
[ 소스 코드 ]
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 <iostream> using namespace std; int N; int arr[21][21]; int ans = 0; void move() //블럭들을 합치고 옮기는 함수 { for (int i = 0; i < N; i++) { int before = 0; int y; int x; for (int j = 0; j < N; j++) { if (before == 0) { //왼쪽 블럭이 합쳐지지 않았을 때 if (arr[i][j] != 0) { //빈 블럭이 아니라면 before = arr[i][j]; //합쳐질 블럭과 비교하기 위해 before 변수에 값을 넣어준다. y = i; //비교를 위해 좌표를 저장 x = j; } } else { if (arr[i][j] != 0) { //왼쪽에 블럭이 있다면 if (before == arr[i][j]) { //충돌하는 블럭의 값이 같다면 arr[y][x] = before * 2; //블럭의 값을 2배로 바꿔주고 arr[i][j] = 0; //충돌한 블럭을 제거 before = 0; //before을 0으로 초기화 시켜준다. } else { //만약 값이 다르다면 before = arr[i][j]; //before을 지금 좌표의 값으로 바꿔주고 y = i; //좌표를 저장한다. x = j; } } } } } for (int i = 0; i < N; i++) { //합치는 과정이 끝나면 int cnt = 0; for (int j = 0; j < N; j++) { //왼쪽에서부터 차례로 if (arr[i][j] != 0) { //빈 블럭이 아니라면 if (cnt != j) { //왼쪽에 빈 공간이 있다면 arr[i][cnt] = arr[i][j]; //왼쪽으로 옮기고 arr[i][j] = 0; //지금 칸을 비워준다. } cnt++; //비어 있는 칸을 오른쪽으로 한칸씩 옮겨준다. } } } } void turn(int num) //num만큼 90도 회전 { int temp[21][21]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { temp[i][j] = arr[i][j]; } } for (int k = 0; k < num; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { arr[i][j] = temp[j][N - i - 1]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { temp[i][j] = arr[i][j]; } } } } void dfs(int level) { if (level == 5) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (arr[i][j] > ans) { ans = arr[i][j]; } } } return; } int temp[21][21]; //백트래킹을 위해 temp배열 선언 for (int i = 0; i < N; i++) { //지금 모습을 temp에 저장 for (int j = 0; j < N; j++) { temp[i][j] = arr[i][j]; } } for (int k = 0; k < 4; k++) { turn(k); move(); //옮긴 후 dfs(level + 1); //다음으로 넘어갔다가 for (int i = 0; i < N; i++) { //나올 때 원상 복구 for (int j = 0; j < N; j++) { arr[i][j] = temp[i][j]; } } } } int main() { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> arr[i][j]; } } dfs(0); cout << ans; } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 1509번 - 팰린드롬 분할 (C++) (0) | 2022.05.26 |
|---|---|
| [ 백준 ] 1208번 - 부분수열의 합 2 (C++) (0) | 2022.05.25 |
| [ 백준 ] 17387번 - 선분 교차 2 (C++) (0) | 2022.05.24 |
| [ 백준 ] 17143번 - 낚시왕 (C++) (0) | 2022.05.23 |
| [ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++) (0) | 2022.05.22 |