[자바] 백준 12100 - 2048 (Easy) (boj java)

문제 : boj12100

 

  (상당히 귀찮은편인) 단순 시뮬레이션 문제이다. 최대 5번 이동이라고 했으므로, 처음 상태에서 상하좌우 4방향으로 움직이는걸 최대 5번 반복하면 된다. 즉, 최대 4^5번으로 모든 경우를 확인할 수 있다. 이 때 각 방향마다 NxN 칸의 모든 것들을 해당방향으로 움직여야 한다고 볼 수 있으므로 대략 O(N^2 x 4^5)의 시간복잡도가 된다.

 

  그럼 남은건 상하좌우 방향으로 움직인다고 할 때, 문제에서 제시된 방법대로 동작만 되도록 시뮬레이션을 구현해주면 된다. 이 때 주의점은 예를들어 아래와 같은 경우를 보자.

2 0 0
2 0 0
2 0 0

위와 같은 경우 우측 방향으로 모두 이동시킨다고 했을 때, 우측으로 모두 붙어야 할 것이다.

[A]
0 2 0
0 2 0
0 2 0

[B]
0 0 2
0 0 2
0 0 2

즉, [A]처럼 되면 안되고 [B]처럼 되야 한다.

 

또한 아래로 내린다고 했을 때 '이동하려고 하는 쪽의 칸이 먼저 합쳐진다.' 라는 지문에 따라

[A]
0 0 0
4 0 0
2 0 0

[B]
0 0 0
2 0 0
4 0 0

[A]가 아니라 [B]가 되어야 한다.

 

 

이번엔 다른 예시를 봐보자.

2 0 0
2 0 0
4 0 0

위의 경우 아래로 내릴 때 

[A]
0 0 0
0 0 0
8 0 0

[B]
0 0 0
4 0 0
4 0 0

[A]라고 생각할 수 있으나, '한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기' 라는 지문에 따라 [B]처럼 해야 한다. 물론 이후에 한번 더 아래로 내리면 [A]가 된다.

 

 

위의 사항들만 주의해서 구현해보자.

내 경우엔 2차원 배열을 1차원 배열로 만들어서 동작시켰다(r행 c열일 경우 1차원 배열에서 r*N+c번). 그 이유는 2차원으로 진행할 경우, 판을 회전시키지 않는이상 편하게 4방향의 움직임을 중복코드 없이 짜기 어렵다고 판단했기 때문이다. 1차원 배열로 바꿈으로써 init() 함수에서만 4방향에 대해 세팅하는 코드가 나뉘고, 이후로는 동일한 코드로 처리할 수 있도록 했다.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Dir {
    int gap;
    ArrayList<Integer> st;
    public Dir(int n, int gap) {
        this.gap = gap;
        st = new ArrayList<>(n);
    }
    public void addSt(int a) {st.add(a);}
}
public class Main {
    private static final int COUNT_LIMIT = 5;
    Dir[] dir = new Dir[4];
    int n, answer = 0;
    int[] arr;
    private void init(int n) {
        dir[0] = new Dir(n, -1);    for (int i = 1; i <= n; i++)            dir[0].addSt(n*i-1);
        dir[1] = new Dir(n, 1);     for (int i = 0; i < n; i++)             dir[1].addSt(n*i);
        dir[2] = new Dir(n, -n);        for (int i = n*(n-1); i < n*n; i++)     dir[2].addSt(i);
        dir[3] = new Dir(n, n);         for (int i = 0; i < n; i++)             dir[3].addSt(i);
    }
    private void setMax() {
        for (int i = 0; i < n*n; i++) answer = Math.max(answer, arr[i]);
    }
    private void bf(int cnt) {
        if (cnt == COUNT_LIMIT) {
            setMax();
            return;
        }
        int[] arrTmp = arr;
        for (int i = 0; i < 4; i++) {
            int gap = dir[i].gap;
            int[] tmp = Arrays.copyOf(arr, arr.length);
            boolean[] dupChk = new boolean[n*n];
            int moveCnt = -1;
            while (moveCnt != 0) {
                moveCnt = 0;
                for (int cur : dir[i].st) {
                    for (int j = 0; j < n - 1; j++) {
                        if (tmp[cur] == 0 && tmp[cur + gap] != 0) {
                            tmp[cur] = tmp[cur + gap];
                            tmp[cur + gap] = 0;
                            dupChk[cur] = dupChk[cur + gap];
                            moveCnt++;
                        } else if (tmp[cur] != 0 && tmp[cur] == tmp[cur + gap] && !dupChk[cur] && !dupChk[cur + gap]) {
                            tmp[cur + gap] = 0;
                            tmp[cur] *= 2;
                            dupChk[cur] = true;
                            moveCnt++;
                        }
                        cur += gap;
                    }
                }
            }
            arr = tmp;
            bf(cnt+1);
            arr = arrTmp;
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        init(n);
        arr = new int[n*n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) arr[i*n+j] = Integer.parseInt(st.nextToken());
        }
        bf(0);
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}