99클럽 코테스터디 37일차 TIL BOJ- 2048(Easy)

2048(Easy)

BOJ Gold l BruteForce
문제 링크

 

문제 설명

2048이라는 게임의 룰에 따라서 주어지는 보드 판을 기준으로 5번 움직였을 때의 최대값을 구하는 문제

문제 풀이

처음 봤을 떄, 5번만 이동하면 되고 최대 20x20 크기라서 완전탐색해도 문제가 없을 것이라 생각해 부담없이 완전탐색으로 풀이했다.

상, 하, 좌, 우로 타일을 이동시키는 과정이 생각보다 더 까다로웠고 매 이동시마다 merged 배열을 선언해 이 칸이 합쳐졌던 칸인지 확인하면서 진행했다.

디버깅에서 상당한 시간을 썼는데 해당 블로그의 테케를 참고했다.
블로그 링크

[c++] 2048 (Easy) (12100), 반례모음, DFS, 백트래킹, 재귀

 

코드

#include <iostream>
#include <vector>

using namespace std;

int N, ret=0;
vector<vector<int>> board;

vector<vector<int>> swipingUp (vector<vector<int>>& pos) {
    vector<vector<int>> res(N, vector<int> (N, 0));

    for (int i=0; i<N; i++) {
        vector<bool> merged(N, false);
        int idx = 0;
        for (int j=0; j<N; j++) {
            if (pos[j][i] > 0) {
                if (idx > 0 && res[idx-1][i] == pos[j][i] && !merged[idx-1]) {
                    res[idx-1][i] *= 2;
                    merged[idx-1] = true;
                }
                else {
                    res[idx][i] = pos[j][i];
                    idx++;
                }
            }
        }
    }
    return res;
}

vector<vector<int>> swipingDown (vector<vector<int>>& pos) {
    vector<vector<int>> res(N, vector<int> (N, 0));

    for (int i=0; i<N; i++) {
        vector<bool> merged(N, false);
        int idx = N-1;
        for (int j=N-1; j>=0; j--) {
            if (pos[j][i] > 0) {
                if (idx < N-1 && res[idx+1][i] == pos[j][i] && !merged[idx+1]) {
                    res[idx+1][i] *= 2;
                    merged[idx+1] = true;
                }
                else {
                    res[idx][i] = pos[j][i];
                    idx--;
                }
            }
        }
    }

    return res;
}

vector<vector<int>> swipingLeft (vector<vector<int>>& pos) {
    vector<vector<int>> res(N, vector<int> (N, 0));

    for (int i=0; i<N; i++) {
        vector<bool> merged(N, false);
        int idx=0;
        for (int j=0; j<N; j++) {
            if (pos[i][j] > 0) {
                if (idx>0 && res[i][idx-1] == pos[i][j] && !merged[idx-1]) {
                    res[i][idx-1] *= 2;
                    merged[idx-1] = true;
                }
                else {
                    res[i][idx] = pos[i][j];
                    idx++;
                }
            }
        }
    }

    return res;
}

vector<vector<int>> swipingRight (vector<vector<int>>& pos) {
    vector<vector<int>> res(N, vector<int> (N, 0));

    for (int i=0; i<N; i++) {
        vector<bool> merged(N, false);
        int idx = N-1;
        for (int j=N-1; j>=0; j--) {
            if (pos[i][j] > 0) {
                if (idx < N-1 && res[i][idx+1] == pos[i][j] && !merged[idx+1]) {
                    res[i][idx+1] *= 2;
                    merged[idx+1] = true;
                }
                else {
                    res[i][idx] = pos[i][j];
                    idx--;
                }
            }
        }
    }

    return res;
}

void ckAll (int cnt, vector<vector<int>>& pos) {
    if (cnt == 5) {
        for (int i=0; i<N; i++) {
            for (int num : pos[i]) {
                ret = max(ret, num);
            }
        }
        return ;
    }

    auto upDir = swipingUp(pos);
    auto downDir = swipingDown(pos);
    auto leftDir = swipingLeft(pos);
    auto rightDir = swipingRight(pos);

    if (upDir != pos) ckAll(cnt + 1, upDir);

    if (downDir != pos) ckAll(cnt + 1, downDir);

    if (leftDir != pos) ckAll(cnt + 1, leftDir);

    if (rightDir != pos) ckAll(cnt + 1, rightDir);
}

int main () {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin >> N;
    if (N == 1) {
        int ans;
        cin >> ans;
        cout << ans << "\n"; return 0;
    }

    board.resize(N);

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int tmp; cin >> tmp;
            board[i].push_back(tmp);
        }
    }

    ckAll(0, board);

    cout << ret << "\n";

    return 0;
}

Python 코드

def swiping_up(pos):
    res = [[0] * N for _ in range(N)]

    for i in range(N):
        merged = [False] * N
        idx = 0
        for j in range(N):
            if pos[j][i] > 0:
                if idx > 0 and res[idx - 1][i] == pos[j][i] and not merged[idx - 1]:
                    res[idx - 1][i] *= 2
                    merged[idx - 1] = True
                else:
                    res[idx][i] = pos[j][i]
                    idx += 1
    return res

def swiping_down(pos):
    res = [[0] * N for _ in range(N)]

    for i in range(N):
        merged = [False] * N
        idx = N - 1
        for j in range(N - 1, -1, -1):
            if pos[j][i] > 0:
                if idx < N - 1 and res[idx + 1][i] == pos[j][i] and not merged[idx + 1]:
                    res[idx + 1][i] *= 2
                    merged[idx + 1] = True
                else:
                    res[idx][i] = pos[j][i]
                    idx -= 1
    return res

def swiping_left(pos):
    res = [[0] * N for _ in range(N)]

    for i in range(N):
        merged = [False] * N
        idx = 0
        for j in range(N):
            if pos[i][j] > 0:
                if idx > 0 and res[i][idx - 1] == pos[i][j] and not merged[idx - 1]:
                    res[i][idx - 1] *= 2
                    merged[idx - 1] = True
                else:
                    res[i][idx] = pos[i][j]
                    idx += 1
    return res

def swiping_right(pos):
    res = [[0] * N for _ in range(N)]

    for i in range(N):
        merged = [False] * N
        idx = N - 1
        for j in range(N - 1, -1, -1):
            if pos[i][j] > 0:
                if idx < N - 1 and res[i][idx + 1] == pos[i][j] and not merged[idx + 1]:
                    res[i][idx + 1] *= 2
                    merged[idx + 1] = True
                else:
                    res[i][idx] = pos[i][j]
                    idx -= 1
    return res

def ck_all(cnt, pos):
    global ret
    if cnt == 5:
        for i in range(N):
            for num in pos[i]:
                ret = max(ret, num)
        return

    up_dir = swiping_up(pos)
    down_dir = swiping_down(pos)
    left_dir = swiping_left(pos)
    right_dir = swiping_right(pos)

    if up_dir != pos: ck_all(cnt + 1, up_dir)
    if down_dir != pos: ck_all(cnt + 1, down_dir)
    if left_dir != pos: ck_all(cnt + 1, left_dir)
    if right_dir != pos: ck_all(cnt + 1, right_dir)

if __name__ == "__main__":
    import sys
    input = sys.stdin.read

    N = int(input().strip())
    if N == 1:
        ans = int(input().strip())
        print(ans)
        sys.exit()

    board = []
    for _ in range(N):
        board.append(list(map(int, input().split())))

    ret = 0
    ck_all(0, board)
    print(ret)

 

회고

 

겉보기엔 간단해 보이는 문제였는데, 골드 1인 이유를 보여주는 문제였다.

문제를 풀고 파이썬으로도 변환 해봤는데, 원래 주언어가 파이썬이였었는데도 생각보다 쉽지않았다.

시간이 있으면 한번씩 해보는게 좋을 것같다.