[프로그래머스] 🗽등대

😎나의풀이

function solution(n, lighthouse) {
    const graph = Array.from({ length: n + 1 }, () => []);
    const visited = new Array(n + 1).fill(false);
    // res[node][0] 해당 노드를 켰을 때 켜져있는 등대의 수
    // res[node][1] 해당 노드를 껐을 때 켜져있는 등대의 수
    const res = Array.from({ length: n + 1 }, () => [0, 0]);

    // 등대 간의 뱃길을 이어줌
    for (let [s, e] of lighthouse) {
        graph[s].push(e);
        graph[e].push(s);
    }

    const stack = [1];
    while (stack.length > 0) {
        const node = stack.pop();
        if (!visited[node]) {
            visited[node] = true;
            stack.push(node);
            // 해당 노드의 자식 탐색
            for (const child of graph[node]) {
                if (!visited[child]) {
                    stack.push(child);
                }
            }
        } else { // 노드 방문 후
            for (const child of graph[node]) {
                // 자식 요소를 켰을 때 켜져있는 등대의 수가 하나 이상이라면
                if (res[child][0] > 0) {
                    res[node][0] += Math.min(res[child][0], res[child][1]); // node를 켰을 때
                    res[node][1] += res[child][0]; // node를 껐을 때
                }
            }
            res[node][0]++;
        }
    }

    return Math.min(res[1][0], res[1][1]);
}