[알고리즘] 백준 12100 Easy // 구현, 대칭구현은 한방향만 만들고 배열회전을 이용하라

* 시행착오

• 제발 문제좀 읽자.
• 앞부터 합쳐야 하므로 아래그림은 모두 틀린 풀이이다.

• 그리고 <-- 한뱡향만 구현하고 회전을 이용하는게 훨씬낫다.
• 틀린코드(초안)

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

int ret;
int n, a[24][24];

void moveup() {
   for(int j=0;j<n;++j) {
      vector<int> v;
      for(int i=n-1;i>=0;--i) {
         if(a[i][j]==0) {
            continue;
         }
         if(i-1>=0 && a[i][j]==a[i-1][j]) {
            v.push_back(2*a[i][j]);
            --i;
         }
         else {
            v.push_back(a[i][j]);
         }
      }
      //초기화
      for(int i=0;i<n;++i) {
         a[i][j]=0;
      }
      
      //todo : vector 역순으로 다시 쓰기
      reverse(v.begin(),v.end());
      for(int i=0;i<v.size();++i) {
         a[i][j]=v[i];
      }
   }
}

void movedown() {
   for(int j=0;j<n;++j) {
      vector<int> v;
      for(int i=0;i<n;++i) {
         if(a[i][j]==0) {
            continue;
         }
         if(i+1<n && a[i][j]==a[i+1][j]) {
            v.push_back(2*a[i][j]);
            ++i;
         }
         else {
            v.push_back(a[i][j]);
         }
      }
      //초기화
      for(int i=0;i<n;++i) {
         a[i][j]=0;
      }
      
      //todo : vector 역순으로 다시 쓰기
      reverse(v.begin(),v.end());
      for(int i=0;i<v.size();++i) {
         a[n-i-1][j]=v[i];
      }
   }
}

void moveright() {
   for(int i=0;i<n;++i) {
      vector<int> v;
      for(int j=0;j<n;++j) {
         if(a[i][j]==0) {
            continue;
         }
         if(j+1<n && a[i][j]==a[i][j+1]) {
            v.push_back(2*a[i][j]);
            ++j;
         }
         else {
            v.push_back(a[i][j]);
         }
      }
      //초기화
      for(int j=0;j<n;++j) {
         a[i][j]=0;
      }
      
      //todo : vector 역순으로 다시 쓰기
      reverse(v.begin(),v.end());
      for(int j=0;j<v.size();++j) {
         a[i][n-j-1]=v[j]; //v[i] 아님에 주의!!!
      }
   }
}

void moveleft() {
   for(int i=0;i<n;++i) {
      vector<int> v;
      for(int j=n-1;j>=0;--j) {
         if(a[i][j]==0) {
            continue;
         }
         if(j-1>=0 && a[i][j]==a[i][j-1]) {
            v.push_back(2*a[i][j]);
            --j;
         }
         else {
            v.push_back(a[i][j]);
         }
      }
      //초기화
      for(int j=0;j<n;++j) {
         a[i][j]=0;
      }
      
      //todo : vector 역순으로 다시 쓰기
      reverse(v.begin(),v.end());
      for(int j=0;j<v.size();++j) {
         a[i][j]=v[j];
      }
   }
}

void go(vector<int> v) {
   for(auto i : v) {
      if(i==0) { //상하좌우
         moveup();
      }
      else if(i==1) {
         movedown();
      }
      else if (i==2) {
         moveleft();
      }
      else if (i==3) {
         moveright();
      }
   }
   int mx=0;
   for(int i=0;i<n;++i) {
      for(int j=0;j<n;++j) {
         mx=max(mx,a[i][j]);
      }
   }
   ret=max(ret,mx);
}

void combi(int idx, vector<int> v) {
   if(v.size()==5) {
      // for(auto i : v) {
      //    cout<<i<<" ";
      // }cout<<"\n";
      go(v);
      return;
   }
   for(int i=0;i<4;++i) { //4개(상하좌우)에서 중복포함 5개뽑기
      v.push_back(i);
      combi(i,v);
      v.pop_back();
   }
}

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>>a[i][j];
      }
   }
   // moveup();
   // movedown();
   // moveleft();
   // moveright();
   // for(int i=0;i<n;++i) {
   //    for(int j=0;j<n;++j) {
   //       cout<<a[i][j]<<" ";
   //    }cout<<"\n";
   // }
   
   vector<int> v;
   combi(-1,v);
   cout<<ret;
   
   return 0;
}

 

* 정답풀이1(내껄 수정)

• 맞은점 :
  • 상하좌우 4H5 (상상상상상 ~ 상상상상하 , ... 우우우우우) = (9-1)C5
• 틀린점
  • moveleft함수가 잘못됨
  • 같은게있으면 좌측부터 합쳐야함
  • 2 2 2 -> 4 2 가 되야함
• 비효율
  • 일일히 4방향 move함수를 만듬
  • left만 만들고 회전돌리는게 나음
• moveleft함수 이해
  • c=-1부터 시작 (tmp에 넣을위치)
  • d= 합칠수있는지 표시
  • 원본이 0 -> pass
  • 합칠수있고 원본과 채울위치가 같으면 2배, d=0
  • else 채울위치에 넣으셈, d=1
  • 다끝나고 tmp 빈칸에 0 채우기
  • 다끝나고 tmp를 a에 복사

• 회전함수 이해
  • n-j-1은 반시계 회전임
  • 따라서 그림과 같은 순서로 돌아감
  • 상 쪽으로 옮겨야하는경우
    • 3번회전후, move하고 원복!
    • 항상 좌측상태로 원복을 해주는게 중요

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

int ret;
int n, a[24][24], origin[24][24];

void rotate() {
   int temp[24][24];
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++) {
           temp[i][j] = a[n-j-1][i];  // 반시계방향 회전
       }
   }
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++) {
           a[i][j] = temp[i][j];
       }
   }
}

void moveleft() {
   int temp[24][24] = {0,};
   for(int i = 0; i < n; i++) {
       int c = -1;  // 숫자를 채울 위치
       int d = 0;   // 합치기 가능 여부 (1:가능, 0:불가능)
       
       for(int j = 0; j < n; j++) {
           if(a[i][j] == 0) continue;  // 빈 칸은 건너뛰기
           
           if(d && a[i][j] == temp[i][c]) {  
               // 이전 숫자와 현재 숫자가 같고, 합치기가 가능하면
               temp[i][c] *= 2;  // 숫자를 합침
               d = 0;  // 합치기 불가능 상태로 변경
           } else {
               // 새로운 위치에 숫자를 넣음
               temp[i][++c] = a[i][j];
               d = 1;  // 합치기 가능 상태로 변경
           }
       }
       // 남은 부분을 0으로 채움
       for(c++; c < n; c++) temp[i][c] = 0;
   }
   
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++) {
           a[i][j] = temp[i][j];
       }
   }
}

void go(vector<int>& v) {
   for(int dir : v) {
       if(dir == 0) { // 위쪽
           rotate();
           rotate();
           rotate();
           moveleft();
           rotate();
       }
       else if(dir == 1) { // 아래쪽
           rotate();
           moveleft();
           rotate();
           rotate();
           rotate();
       }
       else if(dir == 2) { // 왼쪽
           moveleft();
       }
       else { // 오른쪽
           rotate();
           rotate();
           moveleft();
           rotate();
           rotate();
       }
   }
   
   int mx = 0;
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++) {
           mx = max(mx, a[i][j]);
       }
   }
   ret = max(ret, mx);
}

void bok() {
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++) {
           a[i][j] = origin[i][j];
       }
   }
}

void combi(vector<int>& v) {
   if(v.size() == 5) {
       bok();
       go(v);
       return;
   }
   for(int i = 0; i < 4; i++) {
       v.push_back(i);
       combi(v);
       v.pop_back();
   }
}

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 >> origin[i][j];
       }
   }
   
   vector<int> v;
   combi(v);
   cout << ret;
   
   return 0;
}

 

* 큰돌코드

• 중복조합대신 ,재귀이용
• 구조체 이용, 초기화를 편하게
• 구조체는 매개변수 전달시 값이 복사됨
• 배열은 참조값이 전달

#include<bits/stdc++.h>
using namespace std;
int ret, n;

// 게임판을 표현하는 구조체
struct Board{
    int a[24][24];  // 게임판 배열

    // 게임판을 시계방향으로 90도 회전하는 함수
    void _rotate90(){
        int temp[24][24];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                // (i,j)위치에 (n-j-1,i)위치의 값을 넣어 90도 회전
                temp[i][j] = a[n - j - 1][i];
            }
        }
        memcpy(a, temp, sizeof(a));  // 회전된 결과를 원본 배열에 복사
    }

    // 왼쪽으로 이동하고 같은 숫자는 합치는 함수
    void _move(){
        int temp[24][24];
        for(int i = 0; i < n; i++){
            int c = -1;  // 숫자를 채울 위치
            int d = 0;   // 합치기 가능 여부 (1:가능, 0:불가능)
            
            for(int j = 0; j < n; j++){
                if(a[i][j] == 0) continue;  // 빈 칸은 건너뛰기
                
                if(d && a[i][j] == temp[i][c]){  
                    // 이전 숫자와 현재 숫자가 같고, 합치기가 가능하면
                    temp[i][c] *= 2;  // 숫자를 합침
                    d = 0;  // 합치기 불가능 상태로 변경
                }else{
                    // 새로운 위치에 숫자를 넣음
                    temp[i][++c] = a[i][j];
                    d = 1;  // 합치기 가능 상태로 변경
                }
            }
            // 남은 부분을 0으로 채움
            for(c++; c < n; c++) temp[i][c] = 0;
        }
        memcpy(a, temp, sizeof(a));  // 결과를 원본 배열에 복사
    }

    // 게임판에서 가장 큰 숫자를 찾는 함수
    void get_max(){
        for(int i = 0;i < n; i++){
            for(int j = 0; j < n; j++){
                ret = max(ret, a[i][j]);
            }
        }
    }
};

// 재귀적으로 모든 가능한 이동 조합을 시도하는 함수
void go(Board c, int here){
    if(here == 5){  // 5번 이동했으면
        c.get_max();  // 최대값 갱신
        return;
    }
    
    for(int i = 0; i < 4; i++){
        Board d = c;     // 현재 상태 복사
        d._move();      // 왼쪽으로 이동
        go(d, here + 1);  // 다음 단계 진행
        c._rotate90();    // 90도 회전하여 다른 방향 이동 준비
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;  // 보드 크기 입력
    Board c;   // 게임판 생성
    
    // 초기 상태 입력
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> c.a[i][j];
        }
    }
    
    go(c, 0);  // 게임 시작
    cout << ret << "\n";  // 최대값 출력
    return 0;
}