백준 알고리즘 12100

 

입력 : N * N 크기 2048게임판이 주어졌다.

출력 : 2048게임의 룰에 맟춰 좌우상하로 움직일 수 있을 때, 5번 움직여 만들 수 있는 가장 큰 수

 

풀이

1. vector를 사용해 입력으로 주어진 게임판을 저장

2. 좌우상하로 한번 움직인 후의 게임판의 모습을 반환하는 함수를 각각 정의
    -> 한 숫자는 한 차례에 한 번만 합쳐질 수 있다
        ex) 8 4 2 2 를 오른쪽으로 이동시키면 0 8 4 2가 되어야 함. 0 0 0 16이 되면 안됨
    -> 계산 범위가 0~N-1을 벗어나지 않도록 지정해야 한다.

3. 게임판을 파라미터로 받는 함수 moveBoard에서 좌우상하 모두 이동시켜본다.

4. 좌우상하로 이동시켜본 후의 게임판정보를 사용해 총 4회 moveBoard를 재귀실행해 가장 큰 값을 리턴한다.

5. moveBoard의 기저조건은 재귀실행을 5회 했을 때, 파라미터로 받은 게임판에서 가장 큰 수를 리턴.

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int direction[6];
 
int getMax(int n, vector<vector<int> > board) {
    int max = 0;
 
    for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++)
            if (max<board[i][j])
                max = board[i][j];
 
    return max;
}
 
vector<vector<int> > moveBoardBottom(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = n - 2; j >= 0; j--) {
            if (result[j][i] == 0 || j == n - 1)
                continue;
            else if (result[j + 1][i] == 0) {
                result[j + 1][i] = result[j][i];
                result[j][i] = 0;
                j += 2;
            }
            else if (result[j + 1][i] == result[j][i]) {
                if (!checker[j + 1][i])
                    continue;
 
                checker[j + 1][i] = false;
                result[j + 1][i] *= 2;
                result[j][i] = 0;
            }
        }
    }
 
    return result;
}
 
vector<vector<int> > moveBoardRight(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = n - 2; j >= 0; j--) {
            if (result[i][j] == 0 || j == n - 1)
                continue;
            else if (result[i][j + 1] == result[i][j]) {
                if (!checker[i][j + 1])
                    continue;
 
                checker[i][j + 1] = false;
                result[i][j + 1] *= 2;
                result[i][j] = 0;
            }
            else if (result[i][j + 1] == 0) {
                result[i][j + 1] = result[i][j];
                result[i][j] = 0;
                j += 2;
            }
        }
    }
 
    return result;
}
 
vector<vector<int> > moveBoardUp(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = 1; j<n; j++) {
            if (result[j][i] == 0 || j == 0)
                continue;
            else if (result[j - 1][i] == result[j][i]) {
                if (!checker[j - 1][i])
                    continue;
 
                checker[j - 1][i] = false;
                result[j - 1][i] *= 2;
                result[j][i] = 0;
            }
            else if (result[j - 1][i] == 0) {
                result[j - 1][i] = result[j][i];
                result[j][i] = 0;
                j -= 2;
            }
        }
    }
 
    return result;
}
 
vector<vector<int> > moveBoardLeft(int n, vector<vector<int> > board) {
    vector<vector<int> > result = board;
    vector<vector<bool> > checker;
 
    for (int i = 0; i<n; i++) {
        vector<bool> temp;
        for (int j = 0; j<n; j++)
            temp.push_back(true);
 
        checker.push_back(temp);
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = 1; j<n; j++) {
            if (result[i][j] == 0 || j == 0)
                continue;
            else if (result[i][j - 1] == result[i][j]) {
                if (!checker[i][j - 1])
                    continue;
 
                checker[i][j - 1] = false;
                result[i][j - 1] *= 2;
                result[i][j] = 0;
            }
            else if (result[i][j - 1] == 0) {
                result[i][j - 1] = result[i][j];
                result[i][j] = 0;
                j -= 2;
            }
        }
    }
 
    return result;
}
 
int moveBoard(int n, vector<vector<int> > board, int rn) {
    if (rn == 5)
        return getMax(n, board);
 
    //0:left 1:right 2:up 3:bottom
    vector<vector<int> > movedBoard[4];
    int result[4];
 
    movedBoard[0] = moveBoardLeft(n, board);
    movedBoard[1] = moveBoardRight(n, board);
    movedBoard[2] = moveBoardUp(n, board);
    movedBoard[3] = moveBoardBottom(n, board);
 
    for (int i = 0; i<4; i++) {
        direction[rn] = i;
        result[i] = moveBoard(n, movedBoard[i], rn + 1);
    }
 
    return max(max(result[0], result[1]), max(result[2], result[3]));
}
 
int main() {
    int n;
    vector<vector<int> > board;
 
    cin >> n;
 
    for (int i = 0; i<n; i++) {
        vector<int> tempList;
        for (int j = 0; j<n; j++) {
            int temp;
            cin >> temp;
            tempList.push_back(temp);
        }
        board.push_back(tempList);
    }
 
    cout << moveBoard(n, board, 0);
 
    return 0;
}