[백준] 2048 easy (12100)

12100번: 2048-Easy

코드

gitHub

static class SolutionImpl implements Solution {
  static class GameBoard {
    
    public int[][] cells = new int[boardSize][boardSize];
    
    void rotate90() {
      int[][] rotateTemp = new int[boardSize][boardSize];
      for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardSize; j++) {
          rotateTemp[i][j] = cells[boardSize - j - 1][i];
        }
      }
      System.arraycopy(rotateTemp, 0, cells, 0, rotateTemp.length);
    }

    void move() {
      int[][] moveTemp = new int[boardSize][boardSize];
      for (int i = 0; i < boardSize; i++) {
        int colIndex = -1;
        int isInsert = 0;
        for (int j = 0; j < boardSize; j++) {

          if (cells[i][j] == 0) {
            continue;
          }

          if (isInsert != 0 && cells[i][j] == moveTemp[i][colIndex]) {
            moveTemp[i][colIndex] *= 2;
            isInsert = 0;
          } else {
            moveTemp[i][++colIndex] = cells[i][j];
            isInsert = 1;
          }

        }
        for (colIndex++; colIndex < boardSize; colIndex++) {
          moveTemp[i][colIndex] = 0;
        }
      }
      System.arraycopy(moveTemp, 0, cells, 0, moveTemp.length);
    }

    void getMax() {
      for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardSize; j++) {
          maxCellValue = Math.max(maxCellValue, cells[i][j]);
        }
      }
    }
  }

  static int maxCellValue, boardSize;

  @Override
  public void doMain() throws IOException {
    Scanner scanner = new Scanner(System.in);
    boardSize = scanner.nextInt();
    GameBoard gameBoard = new GameBoard();
    for (int i = 0; i < boardSize; i++) {
      for (int j = 0; j < boardSize; j++) {
        gameBoard.cells[i][j] = scanner.nextInt();
      }
    }
    exploreGamePaths(gameBoard, 0);
    System.out.println(maxCellValue);
  }

  void exploreGamePaths(GameBoard gameBoard, int moveCount) {
    if (moveCount == 5) {
      gameBoard.getMax();
      return;
    }
    for (int i = 0; i < 4; i++) {
      GameBoard nextBoard = new GameBoard();
      System.arraycopy(gameBoard.cells, 0, nextBoard.cells, 0, gameBoard.cells.length);
      nextBoard.move();
      exploreGamePaths(nextBoard, moveCount + 1);
      gameBoard.rotate90();
    }
  }
}

풀이

경우의 수

이 문제의 핵심은 문제가 백트래킹으로 푸는것이라는것을 인식하는 것이다. 블럭이 이동할 수 있는 방향은 총 4가지 : [왼, 오, 위, 아래] 4가지 이다.

방향은 [왼,오,위,아래], [왼,위,오,아래] .. 등 다양하다. 문제에서 5번 움직일 수 있다 했으니 모든 경우의 수는

단순히 한쪽방향으로 5번 방향전환하는 문제가 아니다.

블럭의 이동 방향

방향에 따른 블럭의 이동을 어떻게 구현할 것인가? 첫번쨰 방법으로는 [왼, 오, 위, 아래] 에 관한 로직을 모두 구현하는 것이다. 이 경우 로직엔 문제가 없지만 귀찮은 상황이 펼쳐진다. 바로 [왼, 오, 위, 아래]에 관한 로직을 각각 구현해서 총 4개의 분기가 만들어 진다는 것이다. 좀더 심플하게 생각해 보자. 방향을 바꾸는것이 아닌, 보드를 회전시켜 버린다면 오직 한 방향에 대해서만 이동 로직을 구현하고 해당 로직을 재활용하면 된다.

회전

// 정사각형 배열 오른쪽으로 90도 회전
 void rotateRight90() {
  int[][] rotateTemp = new int[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      rotateTemp[i][j] = cells[n - j - 1][i];
    }
  }
  System.arraycopy(rotateTemp, 0, cells, 0, rotateTemp.length);
}

rotate가 완료된 배열의 값을 임시로 저장하기 위해 rotateTemp배열을 선언한다. 그리고 rotate로직을 수행하며 rotateTemp배열에 저장한다. 그 후 rotateTemp배열의 값을 System.arraycopy를 활용하여 원래 배 cells 에 복사한다.

블럭의 이동 [ 왼쪽으로 이동 ] , 이거 생각하는데 시간 조금 걸림

void move() {
  int[][] moveTemp = new int[boardSize][boardSize];
  for (int i = 0; i < boardSize; i++) {
    int colIndex = -1;
    int isInsert = 0;

    for (int j = 0; j < boardSize; j++) {
      if (cells[i][j] == 0) { // 0인 경우는 볼필요도 없다.
        continue;
      }

     // isInsert !=0 이고(moveTemp[i][colIndex] 에 값이 존재하고), 
     // cells[i][j] 값과 값이 같으면
      if (isInsert != 0 && cells[i][j] == moveTemp[i][colIndex]) {
        moveTemp[i][colIndex] *= 2; // moveTemp[i][colIndex] 의 값을 * 2 처리한다.
        isInsert = 0;
      } else {
        moveTemp[i][++colIndex] = cells[i][j];
        isInsert = 1;
      }
    }
	// 나머지 뒷 부분은 모두 0 으로 채운다.
    for (colIndex++; colIndex < boardSize; colIndex++) {
      moveTemp[i][colIndex] = 0;
    }
  }
  System.arraycopy(moveTemp, 0, cells, 0, moveTemp.length);
}

move가 완료된 배열의 값을 임시로 저장하기 위해 moveTemp배열을 사용한다. move 로직을 수행하며 moveTemp 배열에 값을 저장한다. 작업이 완료되면 System.arraycopy활용 하여 원래 배열 cells 에 복사한다.

완전탐색

 static int maxCellValue, boardSize;

@Override
public void doMain() throws IOException {
  Scanner scanner = new Scanner(System.in);
  boardSize = scanner.nextInt();
  GameBoard gameBoard = new GameBoard();
  for (int i = 0; i < boardSize; i++) {
    for (int j = 0; j < boardSize; j++) {
      gameBoard.cells[i][j] = scanner.nextInt();
    }
  }
  exploreGamePaths(gameBoard, 0);
  System.out.println(maxCellValue);
}

// fromBoard 는 이전 루프에서 넘겨온 nextBoard
void exploreGamePaths(GameBoard fromBoard, int moveCount) {
  if (moveCount == 5) {
    fromBoard.getMax();
    return;
  }
  for (int i = 0; i < 4; i++) {
    GameBoard nextBoard = new GameBoard();
    // for 문이 돌면서 회전한 gameBoard를 nextBoard에 복사.
    System.arraycopy(fromBoard.cells, 0, nextBoard.cells, 0, boardSize);
    nextBoard.move(); // nextBoard 에서 move
    exploreGamePaths(nextBoard, moveCount + 1); //다음 gameBoard 로 nextBoard를 던져줌
    fromBoard.rotate90(); //이전상태를 기억하고있는 fromBoard 회전시키고 루프의 다음 인덱스로 넘어감
  }
}

가능한 모든 경우의 수를 탐색한다. nextBoard 를 사용하는 이유는 완전탐색 알고리즘을 사용시 이전 상태로의 복원이 필요한데 이경우