12100번: 2048 (Easy) (BOJ C/C++)

12100번: 2048 (Easy)

사용 언어: C++

 

이번 문제는 내용이 길고 그림이 많다 보니 직접 백준 페이지를 확인하는 것이 좋을 것 같다.

 

풀이 1

//1. 블록들을 상하좌우로 옮기면서 합치기 구현
//2. 5번 각각 어느 방향으로 옮길건지 -> 백트래킹

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

int n, ans;
int board1[22][22];
int board2[22][22];

void move(int dir){
    switch(dir){
        case 0:
            for(int i=0; i<n; i++){
                int tilted[21] = {}; // board2[i]를 왼쪽으로 기울인 결과를 저장할 변수
                int idx = 0; // tilted 배열에서 어디에 삽입해야 하는지 가리키는 변수
                for(int j=0; j<n; j++){
                    if(board2[i][j] == 0) continue;
                    if(tilted[idx] == 0) // 삽입할 위치가 비어있을 경우
                        tilted[idx] = board2[i][j];
                    else if(tilted[idx] == board2[i][j]) // 같은 값을 갖는 블록이 충돌할 경우
                        tilted[idx++] *= 2;
                    else // 다른 값을 갖는 블록이 충돌
                        tilted[++idx] = board2[i][j];
                }
                for(int j=0; j<n; j++) board2[i][j] = tilted[j]; // board2[i]에 tilted를 덮어씀
            }
            break;

        case 1:
            for(int i=0; i<n; i++){
                int tilted[21] = {}; // board2[i]를 오른쪽으로 기울인 결과를 저장할 변수
                int idx = n-1;
                for(int j=n-1; j>=0; j--){
                    if(board2[i][j] == 0) continue;
                    if(tilted[idx] == 0)
                        tilted[idx] = board2[i][j];
                    else if(tilted[idx] == board2[i][j])
                        tilted[idx--] *= 2;
                    else
                        tilted[--idx] = board2[i][j];
                }
                for(int j=n-1; j>=0; j--) board2[i][j] = tilted[j];
            }
            break;

        case 2:
            for(int j=0; j<n; j++){
                int tilted[21] = {}; // board2[i]를 위로 기울인 결과를 저장할 변수
                int idx = 0;
                for(int i=0; i<n; i++){
                    if(board2[i][j] == 0) continue;
                    if(tilted[idx] == 0)
                        tilted[idx] = board2[i][j];
                    else if(tilted[idx] == board2[i][j])
                        tilted[idx++] *= 2;
                    else
                        tilted[++idx] = board2[i][j];
                }
                for(int i=0; i<n; i++) board2[i][j] = tilted[i];
            }
            break;

        case 3:
            for(int j=0; j<n; j++){
                int tilted[21] = {}; // board2[i]를 아래로 기울인 결과를 저장할 변수
                int idx = n-1;
                for(int i=n-1; i>=0; i--){
                    if(board2[i][j] == 0) continue;
                    if(tilted[idx] == 0) 
                        tilted[idx] = board2[i][j];
                    else if(tilted[idx] == board2[i][j])
                        tilted[idx--] *= 2;
                    else
                        tilted[--idx] = board2[i][j];
                }
                for(int i=n-1; i>=0; i--) board2[i][j] = tilted[i];
            }
            break;
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> board1[i][j];

    for(int tmp=0; tmp<1024; tmp++){
        for(int i=0; i<n; i++)
              for(int j=0; j<n; j++)
                board2[i][j] = board1[i][j];
        int brute = tmp;
        for(int i=0; i<5; i++){
            int dir = brute % 4;
            brute /= 4;
            move(dir);
        }
        for(int i=0; i<n; i++)
              for(int j=0; j<n; j++)
                ans = max(ans, board2[i][j]);
    }
    cout << ans << '\n';

    return 0;
}

 

풀이 2

직접 모든 방향으로 보드를 옮기는 함수를 4개 구현하는 것보다는 보드 자체를 90도 방향 n(0~3)번 돌리고 각각 왼쪽(어느쪽이던 상관없다)으로 다 옮기면 코드 구현도 더 편하고 깔끔하다.

//1. 블록들을 상하좌우로 옮기면서 합치기 구현
//2. 5번 각각 어느 방향으로 옮길건지 -> 백트래킹

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

int n, ans;
int board1[22][22];
int board2[22][22];

//시계 방향 90도 돌리기
void rotate(){
    int tmp[22][22];
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            tmp[i][j] = board2[i][j];
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            board2[i][j] = tmp[n-1-j][i];
}

//옮기기
void move(int dir){
    while(dir--) rotate();
    for(int i=0; i<n; i++){
        int tilted[21] = {}; // board2[i]를 왼쪽으로 기울인 결과를 저장할 변수
        int idx = 0; // tilted 배열에서 어디에 삽입해야 하는지 가리키는 변수
        for(int j=0; j<n; j++){
            if(board2[i][j] == 0) continue; // 애초에 board2가 비어있으면 건들 필요 X
            if(tilted[idx] == 0) // 삽입할 위치가 비어있을 경우
                tilted[idx] = board2[i][j]; board2 값 삽입
            else if(tilted[idx] == board2[i][j]) // 같은 값을 갖는 블록이 충돌할 경우
                tilted[idx++] *= 2; // 값 두배로 올린 후 idx + 1
            else // 다른 값을 갖는 블록이 충돌
                tilted[++idx] = board2[i][j];
        }
        for(int j=0; j<n; j++) board2[i][j] = tilted[j]; // board2[i]에 tilted를 덮어씀
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> board1[i][j];

    for(int tmp=0; tmp<1024; tmp++){
        for(int i=0; i<n; i++)
              for(int j=0; j<n; j++)
                board2[i][j] = board1[i][j];
        int brute = tmp;
        for(int i=0; i<5; i++){
            int dir = brute % 4;
            brute /= 4;
            move(dir);
        }
        for(int i=0; i<n; i++)
              for(int j=0; j<n; j++)
                ans = max(ans, board2[i][j]);
    }
    cout << ans << '\n';

    return 0;
}