[BOJ / C++] 2048 (Easy) (시뮬레이션)

문제링크: https://www.acmicpc.net/problem/12100

 

1. 코드

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

void swipeLeft(vector<vector<int>>& board, int n) {
    for (int i = 0; i < n; i++) {
        vector<int> tmp(n, 0);
        int idx = 0;
        for (int j = 0; j < n; j++) {
            if (board[i][j] != 0) {   
                if (tmp[idx] == 0) tmp[idx] = board[i][j];
                else if (tmp[idx] == board[i][j]) {
                    tmp[idx] = tmp[idx] * 2;
                    idx++;
                }
                else {
                    idx++;
                    tmp[idx] = board[i][j];
                }
            }
        }
        board[i] = tmp;
    }
}

void rotate(vector<vector<int>>& board, int n) {
    vector<vector<int>> tmp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tmp[i][j] = board[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = tmp[n-1-j][i];
        }
    }
}

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

    int n; 
    cin >> n;

    vector<vector<int>> inpBoard(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> inpBoard[i][j];
        }
    }
    
    int mx = 0;
    for (int tmp = 0; tmp < (1 << (2 * 5)); tmp++) {
        vector<vector<int>> board(n, vector<int>(n));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = inpBoard[i][j];
            }
        }
        
        // 4진법 5자리
        int brute = tmp;
        for (int digit = 0; digit < 5; digit++) {
            int dir = brute % 4;
            brute /= 4;
            
            if (dir == 0) { // left swipe
                swipeLeft(board, n);
            }
            else if (dir == 1) { // down swipe
                rotate(board, n);
                swipeLeft(board, n);
                rotate(board, n);
                rotate(board, n);
                rotate(board, n);
            }
            else if (dir == 2) { // right swipe
                rotate(board, n);
                rotate(board, n);
                swipeLeft(board, n);
                rotate(board, n);
                rotate(board, n);
            }
            else if (dir == 3) { // up swipe
                rotate(board, n);
                rotate(board, n);
                rotate(board, n);
                swipeLeft(board, n);
                rotate(board, n);
            }
        }
        
        int localmx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                localmx = max(board[i][j], localmx); 
            }
        }
        mx = max(mx, localmx);
    }
    
    cout << mx;
}

 

 

2. 분석

BOJ 15683 감시: https://sophon.tistory.com/23

[boj_15683.cpp] 감시 (시뮬레이션)

 

BOJ 15683 스티커 붙이기: https://sophon.tistory.com/24

[boj_18808.cpp] 스티커 붙이기 (시뮬레이션)

 

위 두 문제가 섞여있다고 볼 수 있다. 5번 swipe에 대한 완전 탐색을 '감시' 문제의 방법을 사용해 4진수를 이용하면 되고, 각 방향별 swipe 구현은 왼쪽으로 스와이프만 구현하고 전체 보드를 N회 회전시켜 left Swipe하고 원래 방향으로 복구하는 방식으로 구현한다. swipeLeft() 함수 구현시 tmp 배열을 만들고 거기에 스와이프 이후 결과를 저장하고 원본 board에 복사해주는 방식으로 구현하면 편하다.

 

한번에 구현하려 하지 말고, 중간 중간 끊어서 board를 print해서 찍어봐야 오류를 검출해내고 직관적으로 이해하기 쉽다.

 

 

3. 시간복잡도

5번 swipe가 가능하므로 총 방향수는 4^5이고, 각 방향에 대한 회전 연산 rotate가 최대 4번이므로 n^2, swipe 연산이 n^2이다. n은 최대 20이므로 전부 계산하면 4^5 * 5(4 * 20^2 + 20^2) = 1024 * 5(2000) ≒10,000,000 < 10^8으로 1초 이내에 통과가 가능하다.