본문 바로가기

개발/알고리즘

백준 알고리즘 12100

 

입력 : N * N 크기 2048게임판이 주어졌다.

출력 : 2048게임의 룰에 맟춰 좌우상하로 움직일 수 있을 때, 5번 움직여 만들 수 있는 가장 큰 수

 

풀이

1. vector를 사용해 입력으로 주어진 게임판을 저장

2. 좌우상하로 한번 움직인 후의 게임판의 모습을 반환하는 함수를 각각 정의
    -> 한 숫자는 한 차례에 한 번만 합쳐질 수 있다
        ex) 8 4 2 2 를 오른쪽으로 이동시키면 0 8 4 2가 되어야 함. 0 0 0 16이 되면 안됨
    -> 계산 범위가 0~N-1을 벗어나지 않도록 지정해야 한다.

3. 게임판을 파라미터로 받는 함수 moveBoard에서 좌우상하 모두 이동시켜본다.

4. 좌우상하로 이동시켜본 후의 게임판정보를 사용해 총 4회 moveBoard를 재귀실행해 가장 큰 값을 리턴한다.

5. moveBoard의 기저조건은 재귀실행을 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
197
198
199
200
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int direction[6];
 
int getMax(int n, vector<vector<int> > board) {
    int max = 0;
 
    for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++)
            if (max<board[i][j])
                max = board[i][j];
 
    return max;
}
 
vector<vector<int> > moveBoardBottom(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = n - 2; j >= 0; j--) {
            if (result[j][i] == 0 || j == n - 1)
                continue;
            else if (result[j + 1][i] == 0) {
                result[j + 1][i] = result[j][i];
                result[j][i] = 0;
                j += 2;
            }
            else if (result[j + 1][i] == result[j][i]) {
                if (!checker[j + 1][i])
                    continue;
 
                checker[j + 1][i] = false;
                result[j + 1][i] *= 2;
                result[j][i] = 0;
            }
        }
    }
 
    return result;
}
 
vector<vector<int> > moveBoardRight(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = n - 2; j >= 0; j--) {
            if (result[i][j] == 0 || j == n - 1)
                continue;
            else if (result[i][j + 1== result[i][j]) {
                if (!checker[i][j + 1])
                    continue;
 
                checker[i][j + 1= false;
                result[i][j + 1*= 2;
                result[i][j] = 0;
            }
            else if (result[i][j + 1== 0) {
                result[i][j + 1= result[i][j];
                result[i][j] = 0;
                j += 2;
            }
        }
    }
 
    return result;
}
 
vector<vector<int> > moveBoardUp(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = 1; j<n; j++) {
            if (result[j][i] == 0 || j == 0)
                continue;
            else if (result[j - 1][i] == result[j][i]) {
                if (!checker[j - 1][i])
                    continue;
 
                checker[j - 1][i] = false;
                result[j - 1][i] *= 2;
                result[j][i] = 0;
            }
            else if (result[j - 1][i] == 0) {
                result[j - 1][i] = result[j][i];
                result[j][i] = 0;
                j -= 2;
            }
        }
    }
 
    return result;
}
 
vector<vector<int> > moveBoardLeft(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = 1; j<n; j++) {
            if (result[i][j] == 0 || j == 0)
                continue;
            else if (result[i][j - 1== result[i][j]) {
                if (!checker[i][j - 1])
                    continue;
 
                checker[i][j - 1= false;
                result[i][j - 1*= 2;
                result[i][j] = 0;
            }
            else if (result[i][j - 1== 0) {
                result[i][j - 1= result[i][j];
                result[i][j] = 0;
                j -= 2;
            }
        }
    }
 
    return result;
}
 
int moveBoard(int n, vector<vector<int> > board, int rn) {
    if (rn == 5)
        return getMax(n, board);
 
    //0:left 1:right 2:up 3:bottom
    vector<vector<int> > movedBoard[4];
    int result[4];
 
    movedBoard[0= moveBoardLeft(n, board);
    movedBoard[1= moveBoardRight(n, board);
    movedBoard[2= moveBoardUp(n, board);
    movedBoard[3= moveBoardBottom(n, board);
 
    for (int i = 0; i<4; i++) {
        direction[rn] = i;
        result[i] = moveBoard(n, movedBoard[i], rn + 1);
    }
 
    return max(max(result[0], result[1]), max(result[2], result[3]));
}
 
int main() {
    int n;
    vector<vector<int> > board;
 
    cin >> n;
 
    for (int i = 0; i<n; i++) {
        vector<int> tempList;
        for (int j = 0; j<n; j++) {
            int temp;
            cin >> temp;
            tempList.push_back(temp);
        }
        board.push_back(tempList);
    }
 
    cout << moveBoard(n, board, 0);
 
    return 0;
}
cs

'개발 > 알고리즘' 카테고리의 다른 글

백준 알고리즘 14501  (0) 2019.02.16
백준 알고리즘 13458  (0) 2019.02.16
백준 알고리즘 11931  (0) 2019.02.15
백준 알고리즘 14499  (0) 2019.02.15
백준 알고리즘 12100  (0) 2019.02.14