[백준/12100/C] 2048(Easy)

크게 3개의 파트로 나누어서 생각해보아야한다.

1. 좌/우/상/하의 이동을 어떻게 구현할 것인지?

2. 탐색알고리즘을 어떻게 전개할것인가?

3. 최댓값을 판단하는 알고리즘은?

 

2,3은 문제의 태그를 보면 알 수 있다싶이 브루트포스로 해결할 수 있다.

처음에 시간복잡도가 브루트포스를 커버해줄 수 있는지 의문을 가졌지만 GPT님이 계산해주셔서 그냥 그런갑다 납득했다..

 

1.에 대한 해결로는 좌/우로 이동할 때는 temp배열에 변동된 각 행을, 상/하로 이동할 때는 temp배열에 변동된 각 열을 저장해줄 것이다.

 

좌측으로 미는것을 구현해보자면 이러하다 : 

 

board[i][j]가 0이 아닐때 temp에 받을 것인데,

a) 만약에 temp[idx]가 0이면 그냥 입력받고(게임을 생각해보자, 아무것도 없는 부분은 그냥 스킵하고 지나가듯이),

b) temp[idx] == board[i][j]인 상황이라면 2배해주고 idx값을 키운다.

c) 그외의 ( temp[idx] != board[i][j] )인 상황이라면 idx값을 더해주고 입력받는다.

 

이렇게하면 변동된 행을 저장해줄 수 있다.

변동된 행을 원래의 격자배열로 입력시켜주면 해결.

 

우/상/하로 미는것도 같은 방식으로 구현하면 된다.

 

2,3번을 구현하는건 단순하다.

#include <stdio.h>

int N, board[20][20];

void move_left() {
    for (int i = 0; i < N; i++) {
        int temp[20] = {0};
        int idx = 0;
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0) continue;
            if (temp[idx] == 0) temp[idx] = board[i][j];
            else if (temp[idx] == board[i][j]) temp[idx++] *= 2;
            else temp[++idx] = board[i][j];
        }
        for (int j = 0; j < N; j++) board[i][j] = temp[j];
    }
}

void move_right() {
    for (int i = 0; i < N; i++) {
        int temp[20] = {0};
        int idx = N-1;
        for (int j = N-1; j >=0; j--) {
            if (board[i][j] == 0) continue;
            if (temp[idx] == 0) temp[idx] = board[i][j];
            else if (temp[idx] == board[i][j]) temp[idx--] *= 2;
            else temp[--idx] = board[i][j];
        }
        for (int j = 0; j < N; j++) board[i][j] = temp[j];
    }
}

void move_up() {
    for (int j = 0; j < N; j++) {
        int temp[20] = {0};
        int idx = 0;
        for (int i = 0; i < N; i++) {
            if (board[i][j] == 0) continue;
            if (temp[idx] == 0) temp[idx] = board[i][j];
            else if (temp[idx] == board[i][j]) temp[idx++] *= 2;
            else temp[++idx] = board[i][j];
        }
        for (int i = 0; i < N; i++) board[i][j] = temp[i];
    }
}

void move_down() {
    for (int j = 0; j < N; j++) {
        int temp[20] = {0};
        int idx = N-1;
        for (int i = N-1; i >=0; i--) {
            if (board[i][j] == 0) continue;
            if (temp[idx] == 0) temp[idx] = board[i][j];
            else if (temp[idx] == board[i][j]) temp[idx--] *= 2;
            else temp[--idx] = board[i][j];
        }
        for (int i = 0; i < N; i++) board[i][j] = temp[i];
    }
}

void copy(int src[20][20], int dst[20][20]) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dst[i][j] = src[i][j];
}

int max = 0;

void brute(int T){
    if(!T) {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (board[i][j] > max)
                    max = board[i][j];
        return;
    }
    int backup[20][20];
    for (int d = 0; d < 4; d++) {
        copy(board, backup);
        switch (d) {
            case 0: move_left(); break;
            case 1: move_right(); break;
            case 2: move_up(); break;
            case 3: move_down(); break;
        }
        brute(T - 1);
        copy(backup, board); 
    }

}
int main(){
    scanf("%d", &N);
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            scanf("%d", &board[i][j]);
        }
    }
    brute(5); printf("%d", max);
    return 0;
}