[백준] NO.12100 - 2048 (Easy)(C++)

문제

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

풀이

모바일 게임으로 많이 해봤을 법한 2048게임을 구현하는 문제이다. 블록들은 네가지 방향중 한 방향으로 모두 이동 시키는데, 이때 같은 크기의 블록이 있다면 합쳐지면서 두배의 수가 된다. 또한 구현에서 중요한 것이 현재의 이동을 통해 이미 한번 합쳐진 블록은 또 다시 합칠 수가 없다. 이 점을 유의하며 구현해보자.

 

 

 

 일단은 네가지 방향중 왼쪽으로 이동시키는 경우를 구현한 MoveLeft함수를 보자.

void MoveLeft(vector<vector<int>> &board){
  for(int col=0; col<boardSize-1 ; ++col)
    for(int row=0; row<boardSize ; ++row)
 
      if(board[row][col] == 0)
        for(int i=col+1; i<boardSize ; ++i)
          if(board[row][i] != 0){
            board[row][col] = board[row][i];
            board[row][i] =0;
            break;
          }
 
  for(int col =0; col<boardSize-1 ; ++col)
    for(int row =0; row<boardSize ; ++row)
      if(board[row][col] == board[row][col+1] && board[row][col] != 0){
        board[row][col] *=2;
        board[row][col+1] =0;
      }
 
  for(int col=0; col<boardSize-1 ; ++col)
    for(int row=0; row<boardSize ; ++row)
      if(board[row][col] == 0)
        for(int i=col+1; i<boardSize ; ++i)
          if(board[row][i] != 0){
            board[row][col] = board[row][i];
            board[row][i] =0;
            break;
          }
}

첫 for문(line 2~11)으로 column(열)을 순회하며, 각 row(행)에서 board[row][col]이 0으로 숫자가 없다면 같은 행에서 가장 가까운 수를 가져온다(가져온 곳은 0으로 만들어줌). 이를 모든 행,열을 돌며 진행하면 모든 수가 왼쪽으로 정렬된다.

 

 다음 for문(line 13~18)에서는 같은 수끼리 합져주는 기능을 구현한다. 동일하게 모든 행,열을 순회하는데, 만일 board[row][col]와 board[row][col+1] 이 같다면 board[row][col]의 오른쪽 수가 같은 것이므로 서로를 합쳐 board[row][col]를 두배로 만들어 주고 board[row][col+1]는 0으로 만들어준다. 이때 빈칸을 없애주기 위해 오른쪽의 수들을 당겨준다면 합쳐진 블록이 다시 합쳐질 수 있다. 따라서 빈칸을 그대로 두고 다음 열(col)들에 대해서도 동일한 연산을 해주면 블록들은 한번의 이동에서 한번만 합쳐진다.

 

다음으로는 합쳐진 수로 인한 빈칸을 지워주기 위해 첫 for문과 동일한 연산을 수행한다.

 

왼쪽이 아닌 오른쪽, 위, 아래도 해당 함수를 조금만 변형하면 구현할 수 있다. 다만 비슷한 코드들로 구현된 함수가 많아져 재사용성에서는 문제가 있는 코드가 되었다...

 

void CallMoveDir(vector<vector<int>> &board,int num)는 매개변수로 받아온 숫자로 네 방향의 함수를 호출해주는 역할을 한다.

 

 

void Play2048(vector<vector<int>> board,int moveCount)

위의 함수는 최대 5번의 이동을 구현하기 위한 재귀 함수이다. 만약 호출 횟수인 moveCount가 5이상 이라면 해당 게임판의 최대값을 기록한다.

5미만이 라면 네 가지의 이동을 한 번씩 진행한 후 재귀호출을 진행한다. 이때 vector<vector<int>> copy를 통해 현재의 board값을 대입해 주는 이유는 이동 호출로 인해 변경된 게임판이 그대로 남게되면 서로 다른 경우의 수를 구현하지 못하기 때문에 문제를 풀지 못한다. 따라서 복사한 게임판의 데이터인 copy를 CallMoveDir()에 넘기고 CallMoveDir()와 Move함수들은 이값을 참조자(&)로 받아 수행한 연산의 결과를 다음 Play2048(copy, moveCount+1)의 호출로 넘길수 있도록 구현한다.

 

결과: 16ms

 

코드