[BOJ][삼성기출] 백준 12100번 - 2048 (Easy) 풀이

| |
백준 온라인 저지 백준 12100번 - 2048 (Easy) C++ 풀이 (삼성 SW 역량테스트 기출)


문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.


출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.


풀이

한마디로 2048 게임을 구현하는 문제이다. 다만 숫자의 생성을 제외하고 숫자들의 결합과 이동만을 구현하면 된다. 이 문제에서 고려해야 할 2048 의 규칙은 다음과 같다.

  • 보드판 위의 숫자를 상 하 좌 우 로 이동할 수 있으며 한 번 이동 시 모든 숫자들이 같은 방향으로 갈 수 있는 만큼 최대한 이동한다.
  • 숫자들이 이동할 때 같은 숫자끼리 충돌 시 둘이 합쳐져 하나의 블록이 되고 블록의 숫자는 두 블록의 합이 된다.
  • 한 번의 이동으로 하나의 블록이 연쇄적으로 여러번 합쳐질 수 없다.

주로 마지막 조건을 경우가 많으니 주의하자.

위 규칙들을 바탕으로 백트래킹 을 통해 최대 깊이 5 까지의 최대 수를 찾으면 된다.


전체 코드

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
#include <iostream>
using namespace std;

int N, ans;
int board[20][20];
int backupBoard[5][20][20];

int maxNum(){
    int ret=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            ret=max(ret,board[i][j]);
    return ret;
}

void backup(int n){
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            backupBoard[n-1][i][j]=board[i][j];
}

void rollback(int n){
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            board[i][j]=backupBoard[n-1][i][j];
}

void moveUP(){
    bool isPlused[20][20]={false,};
    for(int i=1;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[i][j]==0) continue;
            else if(board[i-1][j]==0){
                int temp=i-1;
                while(temp>0 && board[temp-1][j]==0) temp--;
                if(temp==0 || board[temp-1][j]!=board[i][j]){
                    board[temp][j]=board[i][j];
                    board[i][j]=0;
                }
                else{
                    if(!isPlused[temp-1][j]){
                        board[temp-1][j]*=2;
                        board[i][j]=0;
                        isPlused[temp-1][j]=true;
                    }
                    else{
                        board[temp][j]=board[i][j];
                        board[i][j]=0;
                    }
                }
            }
            else if(board[i-1][j]==board[i][j] && !isPlused[i-1][j]){
                board[i-1][j]*=2;
                board[i][j]=0;
                isPlused[i-1][j]=true;
            }
        }
    }
}

void moveDOWN(){
    bool isPlused[20][20]={false,};
    for(int i=N-2;i>=0;i--){
        for(int j=0;j<N;j++){
            if(board[i][j]==0) continue;
            else if(board[i+1][j]==0){
                int temp=i+1;
                while(temp<N-1 && board[temp+1][j]==0) temp++;
                if(temp==N-1 || board[temp+1][j]!=board[i][j]){
                    board[temp][j]=board[i][j];
                    board[i][j]=0;
                }
                else{
                    if(!isPlused[temp+1][j]){
                        board[temp+1][j]*=2;
                        board[i][j]=0;
                        isPlused[temp+1][j]=true;
                    }
                    else{
                        board[temp][j]=board[i][j];
                        board[i][j]=0;
                    }
                }
            }
            else if(board[i+1][j]==board[i][j] && !isPlused[i+1][j]){
                board[i+1][j]*=2;
                board[i][j]=0;
                isPlused[i+1][j]=true;
            }
        }
    }
}

void moveLEFT(){
    bool isPlused[20][20]={false,};
    for(int i=1;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[j][i]==0) continue;
            else if(board[j][i-1]==0){
                int temp=i-1;
                while(temp>0 && board[j][temp-1]==0) temp--;
                if(temp==0 || board[j][temp-1]!=board[j][i]){
                    board[j][temp]=board[j][i];
                    board[j][i]=0;
                }
                else{
                    if(!isPlused[j][temp-1]){
                        board[j][temp-1]*=2;
                        board[j][i]=0;
                        isPlused[j][temp-1]=true;
                    }
                    else{
                        board[j][temp]=board[j][i];
                        board[j][i]=0;
                    }
                }
            }
            else if(board[j][i-1]==board[j][i] && !isPlused[j][i-1]){
                board[j][i-1]*=2;
                board[j][i]=0;
                isPlused[j][i-1]=true;
            }
        }
    }
}

void moveRIGHT(){
    bool isPlused[20][20]={false,};
    for(int i=N-2;i>=0;i--){
        for(int j=0;j<N;j++){
            if(board[j][i]==0) continue;
            else if(board[j][i+1]==0){
                int temp=i+1;
                while(temp<N-1 && board[j][temp+1]==0) temp++;
                if(temp==N-1 || board[j][temp+1]!=board[j][i]){
                    board[j][temp]=board[j][i];
                    board[j][i]=0;
                }
                else{
                    if(!isPlused[j][temp+1]){
                        board[j][temp+1]*=2;
                        board[j][i]=0;
                        isPlused[j][temp+1]=true;
                    }
                    else{
                        board[j][temp]=board[j][i];
                        board[j][i]=0;
                    }
                }
            }
            else if(board[j][i+1]==board[j][i] && !isPlused[j][i+1]){
                board[j][i+1]*=2;
                board[j][i]=0;
                isPlused[j][i+1]=true;
            }
        }
    }
}

void direction(int opt){
    switch(opt)
    {
    case 0: moveUP(); break;
    case 1: moveDOWN(); break;
    case 2: moveLEFT(); break;
    case 3: moveRIGHT(); break;
    }
}

// 백트래킹을 이용한 완전탐색
void move(int n){
    ans=max(ans,maxNum());
    if(n==0) return;
    for(int i=0;i<4;i++){
        backup(n);
        direction(i);
        move(n-1);
        rollback(n);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>N;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>board[i][j];

    move(5);

    cout<<ans;

    return 0;
}
0%