Node.js)백준 12094번: 2048(Hard)

https://www.acmicpc.net/problem/12094

12094번: 2048 (Hard)

 

가지치기 힌트1 . 블록이 이동했을 때(상하좌우로 밀었을 때) 변화가 없다면 그 방향으로 더 이상 진행할 필요가 없다. 

가지치기 힌트2.  n번 이동했을 때 나온 최대값에 2^(10-n)을 곱한 값이 최대값보다 작거나 같다면 더 이상 진행할 필요가 없다

 

백트래킹 하는 건 좀만 생각하면 알 수 있는데, 상하좌우로 미는 부분에서 최적화?가 부족하면 계속 시간초과 뜬다. 

node로 해결한 사람이 없어서 잠깐 golang으로 도망갔는데, 거기서도 상하좌우로 미는 부분을 대충 만들었더니 시간초과 났다.  

 

결국

 

https://justicehui.github.io/ps/2020/06/08/BOJ12094/

백준12094 2048 (Hard)

이 분 풀이 훔쳐서 통과했다. 

 

const fs = require("fs");
const input = fs
        .readFileSync("./dev/stdin")
        .toString()
        .trim()
        .split("\n")
        .map(v => v.trim());
const N = +input.shift();

const board = input.map(v => v.split(' ').map(x => +x));

function left(board){
        let new_board = board.map(v => [...v]);
        let q = [];
        for(let i = 0; i<N; i++){
                for(let j = 0; j<N; j++){
                        if(new_board[i][j]){
                                q.push(new_board[i][j]);
                                new_board[i][j] = 0;
                        }
                }
                let k = 0;
                while(q.length>0){
                        let now = q.shift();
                        if(!new_board[i][k]) new_board[i][k] = now;
                        else if(new_board[i][k] == now) new_board[i][k++] <<= 1;
                        else  new_board[i][++k] = now;
                }
        }
        return new_board;
}

function right(board){
        let new_board = board.map(v => [...v]);
        let q = [];
        for(let i = 0; i<N; i++){
                for(let j = N-1; j>=0; j--){
                        if(new_board[i][j]){
                                q.push(new_board[i][j]);
                                new_board[i][j] = 0;
                        }
                }
                let k = N-1;
                while(q.length>0){
                        let now = q.shift();
                        if(!new_board[i][k]) new_board[i][k] = now;
                        else if(new_board[i][k] == now) new_board[i][k--] <<= 1;
                        else  new_board[i][--k] = now;
                }
        }
        return new_board;
}

function up(board){
        let new_board = board.map(v => [...v]);
        let q = [];
        for(let j = 0; j<N; j++){
                for(let i = 0; i<N; i++){
                        if(new_board[i][j]){
                                q.push(new_board[i][j]);
                                new_board[i][j] = 0;
                        }
                }
                let k = 0;
                while(q.length>0){
                        let now = q.shift();
                        if(!new_board[k][j]) new_board[k][j] = now;
                        else if(new_board[k][j] == now) new_board[k++][j] <<= 1;
                        else new_board[++k][j] = now;
                }
        }
        return new_board;
}

function down(board){
        let new_board = board.map(v => [...v]);
        let q = [];
        for(let j = 0; j<N; j++){
                for(let i = N-1; i>=0; i--){
                        if(new_board[i][j]){
                                q.push(new_board[i][j]);
                                new_board[i][j] = 0;
                        }
                }
                let k = N-1;
                while(q.length>0){
                        let now = q.shift();
                        if(!new_board[k][j]) new_board[k][j] = now;
                        else if(new_board[k][j] == now) new_board[k--][j] <<= 1;
                        else  new_board[--k][j] = now;
                }
        }
        return new_board;
}


function getMax(board) {
        let now_max = 0;
        for (let i = 0; i < N; i++) {
                for (let j = 0; j < N; j++) {
                        now_max = now_max > board[i][j] ? now_max : board[i][j];
                }
        }
        return now_max;
}

function isSame(board, new_board) {
        for (let i = 0; i < board.length; i++) {
                for (let j = 0; j < board.length; j++) {
                        if (board[i][j] != new_board[i][j]) {
                                return false;
                        }
                }
        }
        return true;
}



let answer = getMax(board);

function run(board, cnt) {
        const now_max = getMax(board);
        
        if (cnt == 10) {
                answer = Math.max(answer, now_max);
        }
        if(now_max * (1<< 10-cnt) <= answer) return;

        for (let i = 0; i < 4; i++) {
                let new_board;
                switch (i) {
                        case 0: new_board = left(board);
                                break;
                        case 1: new_board = right(board);
                                break;
                        case 2: new_board = up(board);
                                break;
                        case 3: new_board = down(board);
                                break;

                }

                if (isSame(board, new_board)) continue;
                run(new_board, cnt + 1);

        }
}

run(board, 0);
console.log(answer);