백준 15900 JS 풀이(실패)

구하는 값

누가 이기는지

핵심 아이디어

리프노드까지의 깊이를 다 더해서 홀수면 이기고 짝수면 짐

구현방법

양방향그래프에서 연결리스트의 길이가 1인경우는 루트,리프노드뿐이므로 길이가1일때 cnt에 dep를 더해준다 (시작을 0으로하기때문에 루트노드를 제외해줄 필요없음)

코드

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n')

const n = Number(input[0]);
const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= n - 1; i++) {
    const [a, b] = input[i].split(" ").map(Number);
    graph[a].push(b);
    graph[b].push(a);
}

// console.log(graph);
const visitied = new Array(n + 1).fill(false);

let cnt = 0;
function dfs(cur, dep) {
    if (graph[cur].length === 1) cnt += dep;
    visitied[cur] = true;

    for (const next of graph[cur]) {
        if (!visitied[next]) {
            dfs(next, cur, dep + 1);
        }
    }
    // console.log("dep", cur, dep);
}

dfs(1, 0);

console.log(cnt % 2 === 1 ? "Yes" : "No");

시간초과가 뜬다,,,도데체 왜!