[Javascript/PGS] Lv.3 : 등대 - js 런타임에러 해결법

 

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

 

---

프로그래머스 레벨 3 등대 문제 - 트리 dp, dfs 유형

* 정답 풀이는 최하단에

 

1. 재귀 풀이 - DFS

이 풀이는 트리 dp 문제의 정석인 느낌인데, js로는 풀 수 없다.

파이썬의 경우에는 sys.setrecursionlimit를 사용한다면, 재귀의 최대 깊이를 설정할 수 있어서

이렇게 풀면 되지만...

자스는 그런거 없다고 함

 

이 풀이로 제출 시 93.8점이 나왔다. (테스트 9만 틀림)

 

let dp = null;
let visited = null;
let graph = null;

function dfs(node){
    visited[node] = true;
    dp[node][1] += 1;
    for(let i=0; i<graph[node].length; ++i){
        let child = graph[node][i];
        if(visited[child]) continue;
        dfs(child); // 자식 노드 방문
        dp[node][0] += dp[child][1]; // 부모가 안 켜지면 자식이 켜져야 함
        dp[node][1] += Math.min(dp[child][0],dp[child][1]) // 켜지면 자식의 최솟값을 더함
    }
}

function solution(n, lh) {
    visited = new Array(n+1).fill(false);
    graph = new Array(n+1).fill(null).map(()=>[]);
    dp = new Array(n+1).fill(null).map(()=>[0,0]);
    lh.map((l)=>{
        graph[l[0]].push(l[1]);
        graph[l[1]].push(l[0]);
    });
    dfs(1);

    if(dp[1][0] > dp[1][1]) return dp[1][1];
    return dp[1][0];
}

---

 

그래서..

반복문으로 바꿔줘야 한다.

dfs를 반복문으로 만드는 건 처음인데, stack을 사용한 while 루프를 이용하면 된다고 함

 

JS의 재귀는 현재 노드의 부모노드로 돌아가는 로직이 없다고 하는 듯..?

그래서 아래 글 처럼 재귀 함수를 수정하는 방법도 있을 것 같다.

https://chamdom.blog/dfs-using-js/

[알고리즘] JavaScript로 구현하는 DFS

 

 

2. while문 풀이

반복문에서는 재귀를 구현하기 위해 stack에서 pop 해줬다가, 첫 방문으로 탐지되면 다시 push해줘야 한다.

 

나의 풀이

// dp[1][0] : 등대 1을 안 켬 -> 연결된 자식노드는 켜져야함
// dp[1][1] : 등대 1을 켬 -> 연결된 자식노드는 상태 무관
// 트리 순회 -> dfs
// dfs지만 javascript는 재귀로 풀면 테스트 9 시간초과 -> 반복문으로 변경
let dp = null;
let visited = null;
let graph = null;

function solution(n, lh) {
    visited = new Array(n+1).fill(false);
    graph = new Array(n+1).fill(null).map(()=>[]);
    dp = new Array(n+1).fill(null).map(()=>[0,0]);
    lh.map((l)=>{
        graph[l[0]].push(l[1]);
        graph[l[1]].push(l[0]);
    });
    
    let stack = [1];
    
    while (stack.length > 0) {
        let node = stack.pop();
        if (!visited[node]) { // 방문 x
            visited[node] = true;
            stack.push(node); // 다시 넣어서 DP 업데이트용
            for (let child of graph[node]) {
                if (!visited[child]) stack.push(child);
            }
        } else { // 다시 방문 시 DP 업데이트
            dp[node][1] += 1;
            for (let child of graph[node]) { // 노드의 자식들
                dp[node][0] += dp[child][1]; // 부모가 OFF면 자식이 ON이어야 함
                dp[node][1] += Math.min(dp[child][0], dp[child][1]); // ON이면 최소값 선택
            }
        }
    }

    if(dp[1][0] > dp[1][1]) return dp[1][1];
    return dp[1][0];
}