[JavaScript] 백준 15900 나무 탈출

SanE·2025년 2월 25일

DFS JavaScript algorithm number

Algorithm

목록 보기

124/127

수강 과목

📚 문제 설명

트리가 주어진다.
1번이 무조건 부모 노드이다.
리프 노드에는 게임말이 있다.
각각의 플레이어는 한턴에 하나의 말을 부모 노드로 움직인다.
게임말이 1번 노드에 도착하면 제거한다.
플레이어턴에 움직일 말이 없으면 패배.

👨🏻‍💻 풀이 과정

아래 그림처럼 부모 노드인 1번을 기준으로 1-2-3-4 로 연결되어 있는 트리라고 가정해보자.

1
|
2
|
3
|
4

해당 게임에서 언제나 내가 먼저 시작한다고 했을 때,
4 -> 3 : 나
3 -> 2 : 상대
2 -> 1(탈출) : 나
이렇게 되면 상대가 움직일 말이 없이 때문에 무조건 내가 승리하게 된다.

따라서 부모노드부터 리프노드의 길이의 합이 홀수면 나의 승리, 짝수면 상대의 승리이다.

💡성공한 풀이

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

const N = input.shift() * 1;
const trees = Array.from({length: N + 1}, _ => new Array());
const visited = Array(N + 1).fill(false);
input = input.map(v => v.split(' ').map(Number));

input.forEach(v => {
    const [start, end] = v;
    trees[start].push(end);
    trees[end].push(start);
});

let answer = 0;
const dfs = (now, depth) => {
    visited[now] = true;
    if (now !== 1 && trees[now].length === 1) {
        answer += depth;
        return;
    }

    for (const next of trees[now]) {
        if (!visited[next]){
            dfs(next, depth + 1);
        }
    }
};

dfs(1, 0);

console.log(answer % 2 === 1 ? 'Yes' : 'No');

위의 풀이를 완성하기 전까지 수많은 시도들이 있었다.

💡실패한 풀이 (시간 초과)

우선 아래 두 코드를 비교해보자.

통과

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

const N = input.shift() * 1;
const trees = Array.from({length: N + 1}, _ => new Array());
const visited = Array(N + 1).fill(false);

실패

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

const N = Number(input.shift());
const trees = Array.from({length: N + 1}, _ => new Array());
const visited = Array(N + 1).fill(false);

두 코드의 가장 큰 차이점은 입력의 N을 받을 때 실패의 경우 Number()를 이용했다는 것이다.
Number()를 사용할 경우 내부적으로 타입 체크와 복잡한 과정을 거치게 된다고 한다.
하지만 * 1 연산의 경우 단순한 강제 형변환을 진행한다고 한다.

Number() 내부 동작

입력 유형 확인

undefined는 NaN으로 변환됩니다.

null은 0으로 변환됩니다.

boolean 값은 true는 1, false는 0으로 변환됩니다.

이미 number 타입인 경우 그대로 반환됩니다.

문자열 변환 과정 (가장 복잡한 부분):

앞뒤 공백을 제거합니다.

빈 문자열은 0으로 변환됩니다.

16진수 형식(0x로 시작)을 확인하고 파싱합니다.

8진수나 2진수 형식을 확인하고 파싱합니다.

문자열이 유효한 숫자 형식인지 검증하고, 소수점, 지수 표기법 등을 처리합니다.

숫자로 변환할 수 없는 문자열은 NaN을 반환합니다.

객체 변환:

valueOf() 메서드를 호출하여 원시 값을 얻으려고 시도합니다.

원시 값을 얻지 못하면 toString() 메서드를 호출합니다.

이후 얻은 원시 값으로 다시 위의 과정을 반복합니다.

정밀도 및 범위 처리:

JavaScript는 IEEE 754 부동소수점 표준을 사용하므로, 변환된 숫자가 이 범위를 벗어나면 Infinity 또는 -Infinity로 처리합니다.

따라서 동일한 코드에 Number()를 사용할 경우 위의 결과처럼 시간 초과가 발생한다.

그 외에도 Array.from({length: N + 1}, _ => new Array());의 경우와
Array.from({length: N + 1}, _ => []); 를 비교해보면
new Array()로 할당할 경우가 더 빠르게 나왔지만, 이부분은 환경에 따라 다르다고 한다.