2048(Easy)

작성일 | In

[백준] 12100번 - 2048(Easy)

문제 링크

특별한 알고리즘이 필요한 문제는 아니다. 문제를 잘 읽고 그대로 구현하는 문제이다.

브루트포스로 가능한 모든 경우의 수를 탐색했으며, 게임판의 상태를 기준으로 이를 상, 하, 좌, 우로 움직이는 네 가지 경우의 수가 존재한다.

게임판을 움직이는 방식은 아래와 같이 구현했다.

  1. 블록을 이동시키는 방향을 기준으로 순서대로 탐색한다.
    예를 들어, 블록을 위로 이동시킨다면, y=0(게임판 최상단)에서부터 n-1(게임판 최하단)까지 탐색하면서 y=k번째 칸에서 숫자 블록을 찾았다고 가정하자.
    • 이 때, y=k+1번째 칸부터 y=n-1칸까지 탐색하며 k블록 이후 첫 번째로 만나는 블록을 찾는다. k<q<n 인 q번째 칸에서 블록을 찾았다고 가정하자.
      • 만약 q블록이 k블록과 숫자가 동일하다면, k블록을 2배로 만들고 q블록의 수를 0으로 만든다. 그리고 q+1칸 부터 탐색을 이어간다.
      • 만약 q블록이 k블록과 숫자가 다르다면, 아무 연산도 하지 않고 q번째 칸부터 탐색을 이어간다. q번째 칸부터 탐색을 시작하는 이유는, q번째 칸이 m번째 칸(q<m<n)의 블록과 숫자가 일치할 수 있기 때문이다.
    • 만약 k블록 이후 숫자 블록을 찾지 못했다면, 현재 열의 탐색은 종료되고 다음 열을 동일한 방식으로 탐색한다.

    이 방식으로 같은 열 혹은 행에 동일한 숫자 블록 3개 이상이 존재해도 정상적으로 처리할 수 있다.

  2. 1번 작업 이후 남아있는 숫자 블록을 이동시키려는 방향으로 전부 이동시킨다.
  3. 1,2번 작업을 5회 반복한 게임판에서 가장 큰 수를 구하고, 정답 변수와 비교하여 갱신한다.


구현 코드를 보면 알겠지만 상, 하, 좌, 우 움직임 모두 매커니즘은 동일하나 각각 조절해야하는 y,x인덱스 순서가 약간씩 달라 네 가지 경우 모두를 하드 코딩했다.
코드 이해를 돕기 위해 왼쪽으로 이동하는 코드에만 주석을 달았다.

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
208
209
210
211
212
213
214
215
216
#include <bits/stdc++.h>
using namespace std;

int n;

int play(vector<vector<int>> board, int depth) {    

    if(depth == 5) {
        int maxVal = 2;
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                if(maxVal < board[i][j])
                    maxVal = board[i][j];
            }
        }
        return maxVal;
    }

    // 좌
    vector<vector<int>> tempBoard(n); // 게임판을 왼쪽으로 움직일 때 게임판의 변화를 저장할 임시 게임판
    copy(board.begin(), board.end(), tempBoard.begin());

    int maxVal = 2;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            if(tempBoard[i][j] == 0)
                continue;
            
            int nearNum = 0; // board[i][j]와 가장 가까운 숫자 블록의 수를 저장
            int nearIdx = n; // board[i][j]와 가장 가까운 숫자 블록의 x인덱스를 저장
            for(int k=j+1; k<n; ++k) {
                if(tempBoard[i][k] == 0)
                    continue;
                nearNum = tempBoard[i][k];
                nearIdx = k;
                break;
            }

            // 서로 인접한 숫자 블록들의 수가 같다면
            if(tempBoard[i][j] == nearNum) {
                tempBoard[i][j] *= 2;
                tempBoard[i][nearIdx] = 0;
                j = nearIdx; // for문의 ++j에 의해 nearIdx+1부터 탐색하게 됨
            } else {
                j = nearIdx - 1; // for문의 ++j에 의해 nearIdx부터 탐색하게 됨
            }
        }
    }
    // 숫자 블록 이동시키기
    for(int i=0; i<n; ++i) {
        int mvIdx = 0; // 왼쪽으로 이동시켜야 하므로 가장 왼쪽 x인덱스인 0부터 쌓기 시작
        for(int j=0; j<n; ++j) {
            if(tempBoard[i][j] == 0)
                continue;
            if(mvIdx == j) {
                ++mvIdx; // 블럭이 이미 이동시킬 좌표에 위치한다면 mvIdx만 증가
            } else {
                tempBoard[i][mvIdx] = tempBoard[i][j];
                tempBoard[i][j] = 0;
                ++mvIdx;
            }
        }
    }
    int result = play(tempBoard, depth+1);
    maxVal = maxVal < result ? result : maxVal;


    // 우
    copy(board.begin(), board.end(), tempBoard.begin());
    for(int i=0; i<n; ++i) {
        for(int j=n-1; j>=0; --j) {
            if(tempBoard[i][j] == 0)
                continue;
            
            int nearNum = 0;
            int nearIdx = -1;
            for(int k=j-1; k>=0; --k) {
                if(tempBoard[i][k] == 0)
                    continue;
                nearNum = tempBoard[i][k];
                nearIdx = k;
                break;
            }

            if(tempBoard[i][j] == nearNum) {
                tempBoard[i][j] *= 2;
                tempBoard[i][nearIdx] = 0;
                j = nearIdx;
            } else {
                j = nearIdx + 1;
            }
        }
    }
    for(int i=0; i<n; ++i) {
        int mvIdx = n-1;
        for(int j=n-1; j>=0; --j) {
            if(tempBoard[i][j] == 0)
                continue;
            if(mvIdx == j) {
                --mvIdx;
            } else {
                tempBoard[i][mvIdx] = tempBoard[i][j];
                tempBoard[i][j] = 0;
                --mvIdx;
            }
        }
    }
    result = play(tempBoard, depth+1);
    maxVal = maxVal < result ? result : maxVal;


    // 상
    copy(board.begin(), board.end(), tempBoard.begin());
    for(int j=0; j<n; ++j) {
        for(int i=0; i<n; ++i) {
            if(tempBoard[i][j] == 0)
                continue;
            
            int nearNum = 0;
            int nearIdx = n;
            for(int k=i+1; k<n; ++k) {
                if(tempBoard[k][j] == 0)
                    continue;
                nearNum = tempBoard[k][j];
                nearIdx = k;
                break;
            }

            if(tempBoard[i][j] == nearNum) {
                tempBoard[i][j] *= 2;
                tempBoard[nearIdx][j] = 0;
                i = nearIdx;
            } else {
                i = nearIdx - 1;
            }
        }
    }
    for(int j=0; j<n; ++j) {
        int mvIdx = 0;
        for(int i=0; i<n; ++i) {
            if(tempBoard[i][j] == 0)
                continue;
            if(mvIdx == i) {
                ++mvIdx;
            } else {
                tempBoard[mvIdx][j] = tempBoard[i][j];
                tempBoard[i][j] = 0;
                ++mvIdx;
            }
        }
    }
    result = play(tempBoard, depth+1);
    maxVal = maxVal < result ? result : maxVal;


    // 하
    copy(board.begin(), board.end(), tempBoard.begin());
    for(int j=0; j<n; ++j) {
        for(int i=n-1; i>=0; --i) {
            if(tempBoard[i][j] == 0)
                continue;
            
            int nearNum = 0;
            int nearIdx = -1;
            for(int k=i-1; k>=0; --k) {
                if(tempBoard[k][j] == 0)
                    continue;
                nearNum = tempBoard[k][j];
                nearIdx = k;
                break;
            }

            if(tempBoard[i][j] == nearNum) {
                tempBoard[i][j] *= 2;
                tempBoard[nearIdx][j] = 0;
                i = nearIdx;
            } else {
                i = nearIdx + 1;
            }
        }
    }
    for(int j=0; j<n; ++j) {
        int mvIdx = n-1;
        for(int i=n-1; i>=0; --i) {
            if(tempBoard[i][j] == 0)
                continue;
            if(mvIdx == i) {
                --mvIdx;
            } else {
                tempBoard[mvIdx][j] = tempBoard[i][j];
                tempBoard[i][j] = 0;
                --mvIdx;
            }
        }
    }
    result = play(tempBoard, depth+1);
    maxVal = maxVal < result ? result : maxVal;

    return maxVal;
}

int main(void) {
    scanf("%d", &n);

    vector<vector<int>> board;
    board.resize(n);
    for(int i=0; i<n; ++i)
        board[i].resize(n);
    
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j)
            scanf("%d", &board[i][j]);
    }

    printf("%d", play(board, 0));
}
0%