[JS] 백준 12100 : 2048(Easy)

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

12100번: 2048 (Easy)

 

 

📋풀이방법

1. 게임판을 4방향으로 이동하므로 DFS 재귀함수를 사용한다.

2.  각 4방향마다 다른 방법으로 이동을 해야한다.

 -이유는 4방향 모두 이동되는 좌표가 다르다

 -위로 이동시 [0,0] [0,1],[0,2],[0,3] 이 기준이되고, 각 열 [0,0],[0,1],[0,2],[0,3]의 숫자들이 이동과 결합을 해야한다.

3. 각 방향마다 각 열 또는 각 행의 숫자들을 0을 제외하고 새 배열안에 차례로 넣어준다. (각 기준에 순서대로)

4. 그 배열의 숫자들을 순회하면서 앞 뒤 숫자가 같은 숫자면 결합해줘야한다.

 -또다시 새로운 배열에 값을 넣으면서 앞의 숫자와 뒤의 숫자가 같은지 확인한다.

   -배열안에서 결합을 했다면 배열에 차례로 겹합된 숫자를 넣고  순회하던 배열의 뒤의숫자는 0으로 만들어준다.

   -만약 같지 않다면 그대로 다시 새로운 배열에 넣어준다.

 -모든순회를 끝낸 뒤 앞 뒤 숫자를 순회함으로써 반복문이 배열의 마지막 숫자를 못넣을 가능성이 있다. (i<arr.lenght-1)

 -그러므로 마지막 배열의 숫자가 0이 아니라면 꼭 그 숫자도 배열에 차례로 넣어줘야한다.

5. 이를 5번반복을 햇다면 완성된 배열에서 가장 큰 값을 빼주고 비교해준다.

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let n=Number(input.shift());
let arr_E=[];
for(var i=0;i<n;i++){
    arr_E.push(input.shift().split(" ").map(Number));
}

//순회한 행에서 0이아닌 숫자들을 가져옴
function getAccumulatedArray(arr) {
    const result = [];
    //숫자들을 순회하면서
    for (let i = 0; i < arr.length - 1; i++) {
        //만약 아래에서 숫자가 합쳐져서 0이되는 부분이 생기면 넘어가야한다.
        if (arr[i] === 0) continue;
        //만약 앞의숫자가 뒤의숫자와 같다면
        if (arr[i] === arr[i + 1]) {
            //새로운 빈 배열에 *2한 값을 넣고
            result.push(arr[i] * 2);
            //뒤의 숫자를 0으로만든다.
            arr[i + 1] = 0;
        } else {
            //숫자가 같지않으면 그냥 빈배열에 넣어준다.
            result.push(arr[i]);
        }
    }
    //위에서 앞 뒤의 숫자를 비교하므로 반복문을 끝까지 수행하지않는다.
    //그래서 만약 마지막 반복에 숫자가 합쳐지지않아 arr[i+1]을 0으로 만들지 않는다면 맨 뒤의 숫자를 따로 넣어줘야한다.
    if (arr[arr.length - 1] !== 0) result.push(arr[arr.length - 1]);
    
    return result;

}

//왼쪽으로 보낼때
function pushLeft(array) {
    for (let i = 0; i < n; i++) {
        const arr = [];
        //위에서부터 검사하면서 0이 아닌 숫자가 있는 부분을 빈 배열 arr에 넣는다.
        for (let j = 0; j < n; j++) {
            if (array[i][j] !== 0) {
                arr.push(array[i][j]);
                //그리고 보드에 숫자를 0으로 만든다.
                array[i][j] = 0; 
            }
        }
        //만약 순회한 행에 숫자가 있다면(0이아닌 숫자)
        if (arr.length > 0) {
            //같은 숫자는 합해줘야한다.
            const result = getAccumulatedArray(arr);
            //합친 숫자를 다시 보드에 나열한다 (왼쪽부터=> j=0)
            for (let j = 0; j < result.length; j++) {
                array[i][j] = result[j];
            }
        }
    }
    return array;
}
//오른쪽으로 보낼때
function pushRight(array) {
    for (let i = 0; i < n; i++) {
        const arr = [];
        //다른점은 보드의 오른쪽 끝부터 순회한다.
        for (let j = n - 1; j >= 0; j--) {
            if (array[i][j] !== 0) {
                arr.push(array[i][j]);
                array[i][j] = 0;
            }
        }
        if (arr.length > 0) {
            const result = getAccumulatedArray(arr);
            //숫자를 모두 합치면 오른쪽 끝부분부터 차례로 값을 넣어준다.
            for (let j = 0; j < result.length; j++) {
                array[i][n - 1 - j] = result[j];
            }
        }
    }
    return array;
}

//위로 보낼때
function pushUp(array) {
    //위로 이동하므로 1. [0,0], [1.0], [2,0], [3,0] 
    for (let j = 0; j < n; j++) {
        const arr = [];
        
        for (let i = 0; i < n; i++) {
            if (array[i][j] !== 0) {
                arr.push(array[i][j]);
                array[i][j] = 0;
            }
        }
        if (arr.length > 0) {
            const result = getAccumulatedArray(arr);

            for (let i = 0; i < result.length; i++) {
                array[i][j] = result[i];
            }
        }
    }
    return array;
}

//아래로 보낼 때
function pushDown(array) {
    //아래로 이동하므로 1. [3,0], [2,0],[1,0],[0,0]
    for (let j = 0; j < n; j++) {
        const arr = [];
        
        for (let i = n - 1; i >= 0; i--) {
            if (array[i][j] !== 0) {
                arr.push(array[i][j]);
                array[i][j] = 0;
            }
        }
        if (arr.length > 0) {
            const result = getAccumulatedArray(arr);

            for (let i = 0; i < result.length; i++) {
                array[n - 1 - i][j] = result[i];
            }
        }
    }
    return array;
}


let max = 0;

//4방향으로 움직임을 위해 
function moveBlock(array, cnt) {
    //만약 5번 기울였다면
    if (cnt === 0) {
        //배열안의 값중의 최대값을 빼낸다.
        array.forEach((v) => {
            max = Math.max(max, ...v);
        })
        return;
    }
    //기존의 2차원배열 보드를 깊은복사를 한다.
    //4기울기로 재귀함수를 호출한다.
    let arr = array.map((x)=>[...x]);
    arr = pushLeft(arr);
    moveBlock(arr, cnt - 1);

    arr = array.map((x)=>[...x]);
    arr = pushRight(arr);
    moveBlock(arr, cnt - 1);

    arr = array.map((x)=>[...x]);
    arr = pushUp(arr);
    moveBlock(arr, cnt - 1);

    arr = array.map((x)=>[...x]);
    arr = pushDown(arr);
    moveBlock(arr, cnt - 1);
}

moveBlock(arr_E,5);
console.log(max)

 

 

💢어려웠던 점

1. 2차원 배열을 깊은복사를 통해 DFS로 뻗어나가야했다.

2. 움직이는 방향에따라 각 열 또는 행의 모든 숫자들을 새로운 배열에 넣으면서 숫자를 결합하는 방법을 몰랐다.

3. 이 문제는 계속해서 봐줘야할 것 같다.