티스토리 뷰

알고리즘/백준

[백준] 12100번 2048 (Easy)

머어하지 2018. 10. 19. 01:08

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/swtest/Q12100.java

2048 게임을 구현한다. 새로 추가되는 블럭은 없다.
5번의 명령을 했을 때, 최대 숫자를 출력하여라.


처음 생각

생각보다 난해한 문제였다. 완전한 구현문제! 상 하 좌 우로 흔드는 방향을 한개씩 해주면 코드가 너무 길어질 것 같아서 1개로 묶어준 후, 처리를 해주었다.

▶ 좀 더 짧게, 효율적으로 하려면 어떻게 해야할까? 생각해보고 후에 추가해야겠다.


다음 생각

명령 5개를 DFS 탐색을 통해 정하고, 5개가 다 정해지면 원 배열을 복사한 copy[][]를 원 배열로 초기화를 시켜준 후 copy 배열로 명령을 실행하였다.


다다음 생각

상 하 좌 우로 흔들다 보니 다음과 같은 문제가 발생했다. 3칸으로 4 4 8 이 있는경우 왼쪽으로 기울이면 8 8 0 이 되어야지 16 0 0 이 되면 안됐다.

▶ 그래서 방문 체크 배열 visited[][]을 만들어주어, 합처질 경우 해당 칸을 방문체크 해주었다. 이 방문 체크 배열은 매 명령마다 초기화를 시켜주었다.


다다다음 생각

처음에 상 하 좌 우 모든 방향을 하나로 묶어준것이 문제였다. 탐색을 위해 반복문을 0~N 까지 진행하도록 하였는데, 상 좌 는 괜찮았지만 우 하 는 뒤쪽부터 봐주어야지 제대로 합쳐지기 때문이다.

▶ 고민을하다 우와 하 명령이 들어오면 숫자들을 옮겨주기 전에 copy 배열을 뒤집어주었다. 예를들어 우 명령이 들어왔다면 y축 대칭으로 뒤집어주어서 좌 명령을 실행한 뒤 다시 뒤집어주었다. 마찬가지로 하 명령이 들어오면 x축 대칭하여 뒤집어준 뒤, 상 명령을 실행하고 다시 뒤집어 주었다.


방안

1) 좀 더 좋은 방안을 생각해보고 2048 게임이기 때문에 실제 게임 알고리즘을 찾아봐야겠다.


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
package baekjoon.swtest;
 
import java.io.IOException;
import java.util.Scanner;
 
public class Q12100 {
    static int n;
    static int[] dArr;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][n];
        copy = new int[n][n];
        // 방향을 저장하고 있을 arr
        dArr = new int[5];
        visited = new int[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++)
                arr[i][j] = sc.nextInt();
        }
        result = 0;
        init();
        // DFS를 통해 모든 조건 만들어 주기
        solve(0);
        System.out.println(result);
    }
    
    // 상 하 좌 우 모든 경우를 살펴보자, 최대 5번
    static int result;
    private static void solve(int idx) {
        // 방향 5개가 완성되었다면
        if(idx==5) {
            // 새로쓸 배열 초기화
            init();
            for(int i=0;i<5;i++) {
                // 해당 방향으로 기울이기
                twist(dArr[i]);
                init2();
            }
            // 최대 값 찾기
            for(int j=0;j<n;j++) {
                for(int k=0;k<n;k++)
                    result = Math.max(copy[j][k], result);
            }
            return;
        }
        
        // 모든 방향을 만들어보자.
        for(int i=0;i<4;i++) {
            dArr[idx] = i;
            solve(idx+1);
        }
    }
    
    private static void change(int sw) {
        if(sw==2) {
            // 좌우 바꿔주기
            for(int i=0;i<n;i++) {
                for(int j=0;j<n/2;j++) {
                    int t = copy[i][n-j-1];
                    copy[i][n-j-1] = copy[i][j];
                    copy[i][j] = t;
                }
            }
        }else {
            // 상하 바꿔주기
            for(int i=0;i<n/2;i++) {
                for(int j=0;j<n;j++) {
                    int t = copy[n-i-1][j];
                    copy[n-i-1][j] = copy[i][j];
                    copy[i][j] = t;
                }
            }
        }
    }
    
    static int[][] visited;
    // 상 하 좌 우
    static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    private static void twist(int d) {
        // 아래와 오른쪽 인경우 반대로 봐줘야 하므로 뒤집어 주자
        boolean dFlag = false;
        if(d==3) {
            change(2);
            dFlag = true;
            d=2;
        }else if(d==1) {
            change(0);
            dFlag = true;
            d=0;
        }
        for(int j=0;j<n;j++) {
            for(int i=0;i<n;i++) {
                if(copy[i][j]==0) continue;
                int tx = i+dir[d][0];
                int ty = j+dir[d][1];
                // 범위 벗어났으면 그대로
                if(tx<0 || ty<0 || tx>=n ||ty>=n) continue;
                // 다음께 0이라면 -> 0이 아닐때까지 찾아주자
                boolean flag = false;
                if(copy[tx][ty]==0) {
                    while(copy[tx][ty]==0) {
                        tx = tx+dir[d][0];
                        ty = ty+dir[d][1];
                        if(tx<0 || ty<0 || tx>=n ||ty>=n) {
                            // 범위를 넘어가면 전꺼로 돌려주기
                            tx = tx-dir[d][0];
                            ty = ty-dir[d][1];
                            flag = true;
                            break;
                        }
                    }
                    // 끝 부분 도착일 경우
                    if(flag) {
                        copy[tx][ty] = copy[i][j];
                        copy[i][j] =0;
                        continue;
                    }
                    // 0이 아니면 나오게 된다. -> 같은지 보고 결정
                    if((copy[tx][ty]==copy[i][j])&&visited[tx][ty]==0) {
                        // 같다면 합쳐주기
                        copy[tx][ty]*=2;
                        // 현재 것은 0으로
                        copy[i][j]=0;
                        // 이번에 합친곳 방문 처리
                        visited[tx][ty] = 1;
                    }else {
                        // 다르다면 전 것 까지 옮겨주기
                        tx = tx-dir[d][0];
                        ty = ty-dir[d][1];
                        copy[tx][ty] = copy[i][j];
                        copy[i][j] = 0;
                    }
                }else {
                    // 다음께 0이 아니라면-> 같은지 보고 결정
                    if((copy[tx][ty]==copy[i][j])&&visited[tx][ty]==0) {
                        // 같다면 합쳐주기
                        copy[tx][ty]*=2;
                        // 현재 것은 0으로
                        copy[i][j]=0;
                        // 이번에 합친곳 방문 처리
                        visited[tx][ty] = 1;
                    }
                }
            }
        }
        if(dFlag) change(d);
    }
    private static void init2() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++)
                visited[i][j]=0;
        }
    }
    
    static int[][] copy;
    private static void init() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++)
                copy[i][j]=arr[i][j];
        }
    }
}
 


'알고리즘 > 백준' 카테고리의 다른 글

[백준] 13460번 구슬 탈출2  (4) 2018.10.20
[백준] 15683번 감시  (2) 2018.10.19
[백준] 14502번 연구소  (0) 2018.10.18
[백준] 14890번 경사로  (0) 2018.10.18
[백준] 14499번 주사위 굴리기  (2) 2018.10.17
공유하기 링크
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday