프로그래밍/알고리즘 풀이

[node.js] 욕심쟁이 판다 ( 백준 1937번 )

카카수(kakasoo) 2021. 4. 14. 22:58
반응형

시간 초과를 해결했더니, 공간 복잡도가 높아지는 문제가 있었다. 일반적으로, dfs로 해서 해결될만한 문제 같은데,

35% 이상을 넘어가면 런타임 에러가 발생했다. ( 중간에 CannotFindModule은 자동완성 때문에 그러하다. )

내 개인적인 생각으로는, 스택 영역이 고갈되었기 때문이다.

사실, StackSizeExceeded라고 써있으니 당연한 거 아닌가, 생각할 수 있겠지만, 그래도 생각해볼 부분이 나름 있다.

자바스크립트의 변수는 다른 언어들보다 좀 크다.

숫자의 경우의 8바이트, 기본적으로 모든 숫자가 double이기 때문이다.

그러니깐 잘 짜려고 노력해도 남들보다 변수를 2배 이상 가지고 있으니, 똑같은 함수여도 가끔씩 stack이 고갈된다.

따라서 정적인 영역 ( 데이터 영역 )으로 조금 돌릴 필요가 있는데, 이러면 또 코드를 대량으로 고쳐야 한다.

결국 dfs 자체를 수정하기로 했다.

사실, 고치고 싶진 않았다. 뭔가 조금만 하면 될 거 같아서, 조금씩 코드를 깎아 내려봤는데 웬걸.

더 이상 깎을 구간도 없었다.

결국 이게 한계겠거니 싶어 ( 혹시 다른 사람들이 해냈다면, 나에게도 링크를 줬으면 한다. ) 결국 방식을 바꿨다.

DP문제처럼 풀었다. 2차원 배열에 대한 DP, 그래프처럼 탐색하는 DP라... 색다르고 재밌었다.

여담인데, 탐색 방향이 상하좌우인지, 상우하좌인지, 방향에 따라서 메모리 사용량이 달라진다고 한다.

물론 잘 만든 알고리즘이라면 그런 요소에 좌우될 것 없이 올바른 결과를 출력해낼 수 있어야 겠지만.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const graph = [];
let N;
rl.on("line", (line) => {
    if (!N) {
        N = Number(line);
    } else {
        const row = line.split(" ").map(Number);
        graph.push(row);

        if (graph.length === N) {
            rl.close();
        }
    }
}).on("close", () => {
    let maxValue = 0;
    const visited = [];
    const xMove = [0, 0, -1, 1];
    const yMove = [1, -1, 0, 0];

    const visitedInit = () => {
        for (let i = 0; i < N; i++) {
            visited[i] = new Array(N).fill(false);
        }
    };

    const dfs = (y, x) => {
        if (visited[y][x] === false) {
            visited[y][x] = 1;

            let temp = 0;

            for (let i = 0; i < 4; i++) {
                const nextY = y + yMove[i];
                const nextX = x + xMove[i];

                if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N) {
                    if (graph[y][x] > graph[nextY][nextX]) {
                        temp = Math.max(temp, dfs(nextY, nextX));
                    }
                }
            }
            visited[y][x] += temp;
        }
        return visited[y][x];
    };

    visitedInit();
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (visited[i][j] === false) {
                maxValue = Math.max(maxValue, dfs(i, j));
            }
        }
    }

    // visited.forEach((el) => console.log(el));
    console.log(maxValue);
});

원래 코드는 dfs에 매개변수로 depth를 주었다. 그걸로 depth를 추적해가려고 했었다. DP가 훨씬 낫다.

반응형