BOJ 12100) 2048(Easy) (C++)

 

12100번: 2048 (Easy)

Easy라고 되어있는데 헤맸다. 구현 자체는 어렵지 않았는데 DFS처럼 구현을 해버리고 board는 원상복구를 안시켜줘서 자꾸 오답이 떴다. 매 회 보드의 형태를 기억할 순 없으니까 5번 돌리고 나면 다시 아예 처음으로 돌아가서 시행해줘야 한다. 

큐를 이용해서 각 라인을 표현했다. 앞에 아무것도 없는 경우(temp = 0)에는 해당 값을 기억하고 큐에서 빼낸다. 앞에 블럭이 있는 경우 자신과 같으면 합쳐지면서 board에 덮어씌워지고 다르면 앞의 블럭은 board에 기록되고 큐에서 빠져나온 블럭은 temp로 기록된다. 마지막에 큐가 비워지고 나서 temp에 값이 저장되어 있는 경우 board에 기록해준다. 큐에 넣을 때 board의 값은 0으로 초기화해주었다. 

#include <bits/stdc++.h>
using namespace std;

int N,ans ; 
int board[21][21];
int arr[21][21];
queue<int> q;

void turn(int dir){
  if(dir==1){ // <-
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        if(board[i][j])q.push(board[i][j]);
        board[i][j]=0;
      }
      int temp=0, j=0;      
      while(!q.empty()){
        if(temp==0) {
          temp=q.front();
          q.pop();
        } else if (temp!=0 && temp==q.front()){
          board[i][j++]=temp*2;
          temp=0;
          q.pop();
        } else {
          board[i][j++]=temp;
          temp=q.front();
          q.pop();  
        }
      }
      if(temp!=0) board[i][j]=temp;
    }
  } else if(dir==2){ // 아래
    for(int i=0;i<N;i++){
      for(int j=N-1;j>=0;j--){
        if(board[j][i])q.push(board[j][i]);
        board[j][i]=0;
      }
      int temp=0, j=N-1;      
      while(!q.empty()){
        if(temp==0) {
          temp=q.front();
          q.pop();
        } else if (temp!=0 && temp==q.front()){
          board[j--][i]=temp*2;
          temp=0;
          q.pop();
        } else {
          board[j--][i]=temp;
          temp=q.front();
          q.pop();  
        }
      }
      if(temp!=0) board[j][i]=temp;
    }
  } else if(dir==3){ // ->
    for(int i=0;i<N;i++){
      for(int j=N-1;j>=0;j--){
        if(board[i][j])q.push(board[i][j]);
        board[i][j]=0;
      }
      int temp=0, j=N-1;      
      while(!q.empty()){
        if(temp==0) {
          temp=q.front();
          q.pop();
        } else if (temp!=0 && temp==q.front()){
          board[i][j--]=temp*2;
          temp=0;
          q.pop();
        } else {
          board[i][j--]=temp;
          temp=q.front();
          q.pop();  
        }
      }
      if(temp!=0) board[i][j]=temp;
      temp=0;
    }
  } else if(dir==0){ // 위
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        if(board[j][i]) {
          q.push(board[j][i]);
          board[j][i]=0;
          }
      }
      int temp=0, j=0;      
      while(!q.empty()){
        if(temp==0) {
          temp=q.front();
          q.pop();
        } else if (temp!=0 && temp==q.front()){
          board[j++][i]=temp*2;
          temp=0;
          q.pop();
        } else {
          board[j++][i]=temp;
          temp=q.front();
          q.pop();  
        }
      }
      if(temp!=0) board[j][i]=temp;
    }
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>N;

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cin>>arr[i][j];
    }
  }
  for(int tmp=0; tmp<1024; tmp++){
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        board[i][j]=arr[i][j];
      }
    }
    int brute = tmp;
    for(int i=0;i<5;i++){
      int dir = brute%4;
      brute /=4;
      turn(dir);
    }
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        ans=board[i][j]>ans?board[i][j]:ans;
      }
    }
  }
  cout<<ans;
  return 0;
}