티스토리 뷰

알고리즘 관련/BOJ

BOJ)12100 2048 (Easy)

JASON 자손9319 2017. 3. 30. 18:00

문제:icpc.me/12100


2048 게임에서 가능한 5번의 움직임 이내에 나올 수 있는 가장 큰 블럭을 출력하는 문제이다.


하나의 상태에서 가능한 움직임은 4방향이고 N*N의 모든 블럭이 움직여야 하므로 하나의 상태에서 4방향으로 움직일 때 연산 횟수는 4*N*N이다.


5번 움직일 때 나올 수 있는 모든 횟수는 4^5이므로 모든 경우를 전부 구했을 때 시간 복잡도는 (1024*N^2*4)이므로 완전 탐색으로 해결 가능하다.


이 때 주의해야 할 점은 한번의 움직임에서 이미 합쳐진 블럭은 다시 안합쳐지므로 visited배열을 관리해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, x;
vector<vector<int>> vt;
int bfs() {
    queue<vector<vector<int>>> qu;
    qu.push(vt);
    int ret = 0, c = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            vector<vector<int>> v = qu.front();
            vector<vector<int>> visited(n);
            qu.pop();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    ret = max(ret, v[i][j]);
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> up = v;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int cx = i;
                    while (cx - >= && up[cx - 1][j] == 0)
                        cx--;
                    if (cx - >= && up[cx - 1][j] == up[i][j] && !visited[cx - 1][j]) {
                        up[cx - 1][j] = up[i][j] * 2;
                        up[i][j] = 0;
                        visited[cx - 1][j] = 1;
                    }
                    else 
                        swap(up[cx][j], up[i][j]);
                }
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> down = v;
            for (int i = n - 2; i >= 0; i--) {
                for (int j = 0; j < n; j++) {
                    int cx = i;
                    while (cx + < n&&down[cx + 1][j] == 0)
                        cx++;
                    if (cx + < n&&down[cx + 1][j] == down[i][j] && !visited[cx + 1][j]) {
                        down[cx + 1][j] = down[i][j] * 2;
                        down[i][j] = 0;
                        visited[cx + 1][j] = 1;
                    }
                    else 
                        swap(down[cx][j], down[i][j]);
                }
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> left = v;
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    int cy = j;
                    while (cy - >= && left[i][cy - 1== 0)
                        cy--;
                    if (cy - >= && left[i][cy - 1== left[i][j] && !visited[i][cy - 1]) {
                        left[i][cy - 1= left[i][j] * 2;
                        left[i][j] = 0;
                        visited[i][cy - 1= 1;
                    }
                    else
                        swap(left[i][cy], left[i][j]);
                }
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> right = v;
            for (int i = 0; i < n; i++) {
                for (int j = n - 2; j >= 0; j--) {
                    int cy = j;
                    while (cy + < n&&right[i][cy + 1== 0)
                        cy++;
                    if (cy + < n&&right[i][cy + 1== right[i][j] && !visited[i][cy + 1]) {
                        right[i][cy + 1= right[i][j] * 2;
                        right[i][j] = 0;
                        visited[i][cy + 1= 1;
                    }
                    else
                        swap(right[i][cy], right[i][j]);
                }
            }
            qu.push(up);
            qu.push(down);
            qu.push(left);
            qu.push(right);
        }
        if (c == 5)
            break;
        c++;
    }
    return ret;
}
int main() {
    scanf("%d"&n);
    vt.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d"&x);
            vt[i].push_back(x);
        }
    }
    printf("%d\n", bfs());
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2992 크면서 작은 수  (0) 2017.04.03
BOJ)1058 친구  (0) 2017.04.03
BOJ)12100 2048 (Easy)  (0) 2017.03.30
BOJ)13460 구슬탈출2  (6) 2017.03.30
BOJ)1520 내리막 길  (0) 2017.03.30
BOJ)10422 괄호  (0) 2017.03.30
댓글
댓글쓰기 폼