본문 바로가기
Programming/Algorithm

백준 2048 정답 참고

by OKOK 2018. 4. 10.

1. 일단 큐를 사용해서, 합하는 함수를 만든 것이 대단.

2. dfs 에서 맵을 안가지고 가고, 깊이만 가지고 갑니다.

3. 그래도 리턴되면 해당 뎁스에 따른 map store 를 가지고 있습니다.

4. 변화는 항상 조심스럽게 합니다. merge를 하고 depth 를 +1 합니다.

5. 내부에 들어가서 for 문을돌리도록 합니다. 처음에 들어갈 때, for 문을 들어가지 않고,

6. 최대한 간편하게 짜도록 합니다.

7. 0을 무시하기 위해서 0이면 큐에 넣지 않습니다. 그리고 idx 변수를 사용해서 어떻게 이동하는지를

확실히 합니다.

8. 그리고 큐의 첫번째 데이터를 저장하기 위한 변수를 따로 설정합니다. 

9. dfs 는 가장 간단하게, 최소화 하도록 합니다.


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
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define SIZE 25
int map[SIZE][SIZE];
int n, x, y;
int maxVal;
queue<int> que;
 
void problemIn() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
}
 
void copy_map(int(*a)[SIZE], int(*b)[SIZE]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            b[i][j] = a[i][j];
        }
    }
}
 
void merge(int d) {
 
    if (d == 0) {
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (map[i][j] != 0) que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = n - 1;
            int que_data;
 
            while (!que.empty()) {
                que_data = que.front();
                que.pop();
                if (map[i][idx] == 0) map[i][idx] = que_data;
                else if (map[i][idx] == que_data) {
                    map[i][idx] *= 2;
                    idx--;
                }
                else {
                    idx--;
                    map[i][idx] = que_data;
                }
            }
        }
    }
    else if (d == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0) que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = 0;
            int que_data;
 
            while (!que.empty()) {
                que_data = que.front();
                que.pop();
                if (map[i][idx] == 0) map[i][idx] = que_data;
                else if (map[i][idx] == que_data) {
                    map[i][idx] *= 2;
                    idx++;
                }
                else map[i][++idx] = que_data;
            }
        }
    }
    else if (d == 2) {
        for (int j = 0; j < n; j++) {
            for (int i = n - 1; i >= 0; i--) {
                if (map[i][j] != 0) que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = n - 1;
            int que_data;
 
            while (!que.empty()) {
                que_data = que.front();
                que.pop();
                if (map[idx][j] == 0) map[idx][j] = que_data;
                else if (map[idx][j] == que_data) map[idx--][j] *= 2;
                else map[--idx][j] = que_data;
            }
        }
    }
    else if (d == 3) {
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                if (map[i][j] != 0) que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = 0;
            int que_data;
            while (!que.empty()) {
                que_data = que.front();
                que.pop();
                if (map[idx][j] == 0) map[idx][j] = que_data;
                else if (map[idx][j] == que_data) map[idx++][j] *= 2;
                else map[++idx][j] = que_data;
            }
        }
    }
}
 
void dfs(int depth) {
    if (depth == 5) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maxVal = max(maxVal, map[i][j]);
            }
        }
        return;
    }
 
    int map_store[SIZE][SIZE];
    copy_map(map, map_store);
    for (int i = 0; i < 4; i++) {
        merge(i);
        dfs(depth + 1);
        copy_map(map_store, map);
    }
}
 
int main(void) {
    problemIn();
    dfs(0);
    cout << maxVal << endl;
    return 0;
}
cs

 


저작자표시

관련글

티스토리툴바