[BOJ] 12100 2048(Easy) - JAVA

1. 문제

12100번: 2048 (Easy)

2048 게임은 4 ×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

---

2. 풀이

메인

순서 함수를 부르고, 마지막으로 MAX를 출력한다.

static int N;
static int MAX = 0;

public static void main(String[] args) throws Exception {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   N = Integer.parseInt(in.readLine());
   StringTokenizer st;
   int[][] board = new int[N][N];
   for (int i = 0; i < N; i++) {
      st = new StringTokenizer(in.readLine());
      for (int j = 0; j < N; j++) {
         board[i][j] = Integer.parseInt(st.nextToken());
      }
   }
   order(0,board);
   System.out.println(MAX);
}

 

copyArray, rotate

2차원 배열 복사 함수와 90도 회전 함수다. System.arraycopy에서는 꼭 origin이 아닌 origin[i]를 넣어야 하는 걸 유의해야 한다. 이렇게 넣지 않으면 얕은 복사가 된다.

private static int[][] rotate(int[][] map) {
   int[][] next = new int[N][N];
   for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
         next[j][N-1-i] = map[i][j];
      }
   }
   return next;
}

private static int[][] copyArray(int[][] origin) {
   int[][] next = new int[N][N];
   for (int i = 0; i < N; i++) {
      System.arraycopy(origin[i], 0, next[i], 0, N);
   }
   return next;
}

 

order

n이 5보다 작을 때 4방향으로 움직이고 90도 회전하는 걸 반복한다.

private static void order(int n, int[][] map) {
   if (n == 5) return;
   for (int i = 0; i < 4; i++) {
      move(n,map);//움직이고
      map = rotate(map);//90도 회전
   }
}

 

이동

무조건 왼쪽으로 이동하는 함수다.

1.  먼저 입력받은 map을 복사한다. 이 복사한 배열을 나중에 order에 넘길것이다.

2.  현재 위치가 0이라면 그다음 위치부터 0이 아닌 것을 찾을 때까지 반복한다. 찾으면 바꾸고, 찾지 못한다면 그 가로줄을 끝낸다.

3.  이전 값(prev)을 미리 저장했는데, 이전 값과 현재 copy[i][j]가 동일하다면 합칠 수 있다. copy[i][j-1]에 2를 곱하고 현재 값은 0으로 만든다. prev도 0으로 초기화한다. for 반복문을 사용 중이므로 현재 위치부터 다시 탐색할 수 있도록 --j 한다.

4.  이전 값과 현재 값이 다르다면 이전 값을 현재 값으로 변경한다.

5.  3 또는 4가 끝나면 최댓값을 갱신한다.

6.  모든 탐색이 끝났다면 다음 순서를 위해 order(n+1, 현재배열copy)를 호출한다. 

private static void move(int n, int[][] map) {
   //무조건 왼쪽으로 이동
   int[][] copy = copyArray(map);
   int prev, k;
   for (int i = 0; i < N; i++) {
      prev = -1;
      for (int j = 0; j < N; j ++) {
         if (copy[i][j] == 0) {
            for (k = j; k < N; k ++) {
               if (copy[i][k] != 0) {
                  copy[i][j] = copy[i][k];
                  copy[i][k] = 0;
                  break;
               }
            }
            if (k == N) break;
         }
         if (prev == copy[i][j]) {
            copy[i][j] = 0;
            copy[i][--j] *= 2;
            prev = 0;
         } else {
            prev = copy[i][j];
         }
         MAX = Math.max(MAX, copy[i][j]);
      }
   }

   order(n + 1,copy);

}

---

3. 결과

두 방식으로 풀었다. 한 번은 반복문 start와 증감수를 배열에 미리 저장해놓고 이동하는 방식이었다. 반복문을 줄이기 위해 그런 식으로 풀었다. row가 고정 col 체크, col 고정 row 체크 이 두 경우는 반복문을 같이 쓸 수 없어서 결국 switch case로 for문이 두 번 돌았다.

두 번째 방식은 다른 사람 풀이를 조금 참고했다. 이 글에 있는 방식이고, 시간이 덜 걸린다. 한 방향으로 움직이기만 하고 배열 자체를 돌린다. 이 방식이 좀 더 깔끔한 것 같다.

+ System.arraycopy를 쓰다가 아무 생각 없이 next[i], origin[i]가 아니라 next, origin 이렇게 2차원 배열 통째로 넣었다가 영문도 모르고 틀렸다. 두 번이나..