Easy is Perfect

[백준] 12100번 C/C++ 풀이 _ 2048(Easy)

  • melonicedlatte
  • Apr 02, 2018


문제 출처 : https://www.acmicpc.net/problem/12100 

2048 (Easy) 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초512 MB86531958114221.148%

문제

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

힌트

출처

>> 풀이 방법 

배열에 있는 숫자를 위로 옮기는 함수를 생성한다. 
나머지 아래, 왼쪽, 오른쪽은 배열의 위치를 바꿔서 위로 옮기는 함수를 수행하면 동일한 작업을 할 수 있다. 

이렇게 하는 것이 상대적으로 소스 코드의 작업량을 줄이고, 버그를 줄일 수 있다. 
자세한 설명은 주석으로 잘 설명해 놓았다. 

하지만 시간이 많이 소요되었는데, 런타임 에러 때문이다. 
c/c++ 에서는 배열의 index를 어겨도 그 곳에서 다른 코드가 사용되고 있으면, 
에러를 발생하지 않는다. 

대부분의 프로그래밍에서 해당 경우에 에러가 났는데,
이번에는 나지 않았고 visual studio 에서는 에러가 없다가 xcode 에서는 에러가 나는 등
환경에 따라서도 동일한 코드이지만 다른 차이가 났다. 

>> 주의 사항 및 교훈

- c/c++ 배열을 사용할 때에는 인덱싱 처리를 무조건 해주자 !! 
- 인덱싱 처리가 어려우면 STL을 사용하자. STL 은 자동으로 index 처리를 해준다. 
- 에러가 안 난다고 생각했던 곳에서도 에러가 발생할 수 있으니, 코드 탐색은 제대로
- 항상 모든 숫자 범위까지 고려를 손으로 하고 나서 코딩하기
(인덱싱 처리를 통해 예외 코드는 printf 로 다른 문자 출력하기 )

>> 소스코드

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
200
201
202
203
204
205
206
207
#include <iostream>
#define TRY 5
#define WAY 4
#pragma warning(disable:4996)
using namespace std;
 
int N;
int num_arr[50][50];
 
void print_arr(int arr[][50]) {
    for (int i = 0; i < N; i++){
        for (int k = 0; k < N; k++) {
            printf("%d ", arr[i][k]);
        }
        printf("\n");
    }
    printf("\n");
}
 
// 블록을 위로
void move_blocks_upper() {
    // 컬럼 하나하나씩 살핀다.
    for (int i = 0; i < N; i++) {
        // 0을 가리키는 인덱스와 결합된 인덱스를 가리키는 얘를 설정.
        int zero_index = -2;
        int fusion_index = -2;
        // 컬럼 하나에서 row를 따진다.
        for (int k = 0; k < N; k++) {
            // 만약 0이면
            if (num_arr[k][i] == 0) {
                // zero_index가 설정되어 있지않으면 초기화 한다.
                if (zero_index == -2) zero_index = k;
                // 설정 되어 있으면 계속 넘긴다.
                else continue;
            }
            // 0이 아니면
            else {
                // 이전 인덱스가 로우 시작점이면
                if (zero_index == -2) {
                    zero_index = 1;
                }
                // 이전 인덱스가 로우 시작점이 아니면
                else {
                    // 기존에 변경된 값인지 비교
                    // 변경이 된 값이면 그냥 쌓고 리턴
                    if (fusion_index == zero_index -1) {
                        // 현재 값을 밀어 넣고, zero_index를 한 칸 위로 설정.
                        num_arr[zero_index][i] = num_arr[k][i];
                        num_arr[k][i] = 0;
                        zero_index++;
                    }
                    // 변경이 안 된 값이면, 이전 값과 같은지 비교
                    else {
                        // 같으면 결합하고 결합 인덱스 조정
                        if( zero_index == 0  ){
                            num_arr[zero_index][i] = num_arr[k][i];
                            num_arr[k][i] = 0;
                            zero_index++;
                        }
                        else if(num_arr[zero_index - 1][i] == num_arr[k][i]) {
                            num_arr[zero_index - 1][i] *= 2;
                            num_arr[k][i] = 0;
                            fusion_index = zero_index - 1;
                        }
                        // 다르면 그냥 밀어 넣는다.
                        else {
                            // 현재 값을 밀어 넣고, zero_index를 한 칸 위로 설정.
                            if (zero_index != k){
                                num_arr[zero_index][i] = num_arr[k][i];
                                num_arr[k][i] = 0;
                            }
                            zero_index++;
                        }
                    }
                }
            }
        }
    }
}
 
// 트랜잭션 수행 함수
void transaction() {
    for ( int i = 0 ; i < 2*N-1; i++)
        for (int j = 0; j < (i+1)/2; j++) {
            int a = j, b = i-j;
            // 인덱스 검사
            if ( (a < 0) || (a >= N) ||  (b < 0) || (b >= N) )
                continue;
            int sub = num_arr[a][b];
            num_arr[a][b] = num_arr[b][a];
            num_arr[b][a] = sub;
        }
}
 
// 상하를 변경하는 함수
void up_down_change() {
    for (int i = 0; i< N; i++)
        for (int k = 0; k < N / 2; k++) {
            int a = k, b = (N -1) - k;
            int sub = num_arr[a][i];
            num_arr[a][i] = num_arr[b][i];
            num_arr[b][i] = sub;
        }
}
 
// 상 하 좌 우 (0,1,2,3)
void move_blocks(int now_way) {
    switch (now_way)
    {
        case 0:
            move_blocks_upper();
            break;
        case 1:
            // 상하 변경
            up_down_change();
            // upper change
            move_blocks_upper();
            // 상하 변경
            up_down_change();
            break;
        case 2:
            // 트랜잭션
//            print_arr(num_arr) ;
            transaction();
//            print_arr(num_arr) ;
            // upper change
            move_blocks_upper();
            // 트랜잭션
            transaction();
            break;
        case 3:
            // 트랜젝션,상하
            transaction();
            up_down_change();
            // upper change
            move_blocks_upper();
            // 상하, 트랜젝션
            up_down_change();
            transaction();
            break;
        default:
            break;
    }
}
// 배열 복사
void copy_array(int sub_arr[][50], int isCopyFromBasicToSub) {
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++) {
            if (isCopyFromBasicToSub)
                sub_arr[i][k] = num_arr[i][k];
            else
                num_arr[i][k] = sub_arr[i][k];
        }
}
 
 
int dfs(int depth, int now_way) {
    int answer = 0 ;
    int sub_arr[50][50] = { 0 };
    // 높이가 N 이면 가장 큰 값을 계산한다.
    if (depth == TRY) {
        for (int i = 0; i < N; i++)
            for (int k = 0; k < N; k++) {
//                printf("num_arr = %d\n", num_arr[i][k]);
                if (answer < num_arr[i][k])
                    answer = num_arr[i][k];
            }
        return answer;
    }
    
    // 방향대로 블록들을 빈칸 없이 움직인다.
    move_blocks(now_way);
    //printf("depth : %d // now_way : %d // NUM : %d \n", depth, now_way, NUM);
    //print_arr(arr);
    //printf("depth : %d // now_way : %d  sub!!\n", depth, now_way);
    //print_sub_arr(sub_arr, arr);
    // 배열을 잠시 sub 에 저장
    copy_array(sub_arr, 1);
    for (int k = 0; k < WAY; k++) {
        answer = max(answer, dfs(depth+1, k));
        // 다시 sub에 있는걸 원래 배열에 저장
        copy_array(sub_arr, 0);
    }
    
    return answer;
}
 
int main() {
    cin >> N;
    int answer = 0 ;
    int sub_arr[50][50] = { 0 };
    // 데이터 입력 받기
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
            scanf("%d", &num_arr[i][k]);
    // 배열을 잠시 sub 에 저장
    copy_array(sub_arr, 1);
    for (int k = 0; k < WAY; k++) {
        answer = max ( answer, dfs(0, k)) ;
        // 다시 sub에 있는걸 원래 배열에 저장
        copy_array(sub_arr, 0);
        if (k == WAY -1 )
            printf("%d", answer);
    }
    
    return 0;
}
cs
<script src="https://gist.github.com/melonicedlatte/87537bce9a5be6fce32a5ad74529dcf3.js"></script>



Search