소프티어

JS 엔진 스택 크기가 20KB로 나와서.... 런타임 에러가 뜨는거 같습니다.

그냥 객체로 해서 힙에 직접 콜스택을 저장해서 사용하게 바꿨습니다.

추가로, 가중치 합이 js Number에서 오버플로우가 나는 듯합니다? BigInt 써야합니다?

// 입력처리
const fs = require('fs')
const input = fs.readFileSync('input.txt', 'utf8')
    .trim()
    .split(/\n+/)
const nodeCount = +input[0]
const edges = input.slice(1).map(v => v.trim().split(' ').map(Number))
const edgesObj = {}
const weightSum = Array.from({length: nodeCount + 1}, () => [0n, 0])
let rootNode = null
edges.forEach(edge => {
    const [n, m, w] = edge
    if (rootNode === null) rootNode = n
    if (n in edgesObj) {
        edgesObj[n].push([m, w])
    }
    else {
        edgesObj[n] = [[m, w]]
    }
    if (m in edgesObj) {
        edgesObj[m].push([n, w])
    }
    else {
        edgesObj[m] = [[n, w]]
    }
})


function getWeightFromChild(node, child, w) {
    const [childW, count] = weightSum[child]
    weightSum[node] = [childW + BigInt(count + 1) * BigInt(w) + weightSum[node][0], count + 1 + weightSum[node][1]]
}


function getWeightFromParent(parent, node, w) {
    // 전체 가중치에서
    // 그 외의 노드 개수 만큼 부모 ~ 본인 거리 가중치 더하기
    let totalSum = weightSum[parent][0]
    // 자기 자신, 자식 노드의 개수 만큼  부모 ~ 본인 거리 가중치 빼기
    totalSum -= BigInt(w) * BigInt(weightSum[node][1] + 1)
    // 본인, 자식 제외한 노드와의 거리를 위해 나머지 노드 개수 만큼 더하기
    totalSum += BigInt(w) * BigInt(nodeCount - weightSum[node][1] - 1)
    weightSum[node] = [totalSum, weightSum[node][1]]
}


function dfs(node, parent, callbackF, endCallbackF) {
    // dfs 호출 대기
    // dfs 스택
    const callStack = [{
        parameter: [node, parent, 0],
        pendingCallStackParameter: [],
        isExecuted: false
    }]


    while (callStack.length > 0) {
        const currentStack = callStack[callStack.length - 1]
        const [currentN, parentN, weight] = currentStack.parameter


        // 함수가 실행된 후
        if (currentStack.isExecuted) {
            // 콜스택  추가
            if (currentStack.pendingCallStackParameter.length > 0) {
                callStack.push({
                    parameter: currentStack.pendingCallStackParameter.pop(),
                    pendingCallStackParameter: [],
                    isExecuted: false
                })
            }
            // 실행 대기 함수가 없으면,
            else {
                if (parentN !== null && endCallbackF !== null) {
                    endCallbackF(parentN, currentN, weight)
                }
                // return
                callStack.pop()
            }
            continue
        }


        // 실행 기록
        currentStack.isExecuted = true
        if (parentN !== null && callbackF !== null) {
            callbackF(parentN, currentN, weight)
        }


        if (edgesObj[currentN] !== undefined) {
            // 실행해야할 함수 추가
            edgesObj[currentN].forEach(edge => {
                const [childN, w] = edge
                if (childN !== parentN) {
                    currentStack.pendingCallStackParameter.push([childN, currentN, w])
                }
            })
        }
    }
}


// 1을 루트 노드로 하기
dfs(rootNode, null, null, getWeightFromChild)
dfs(rootNode, null, getWeightFromParent, null)
const result = []
for (let i = 1; i < weightSum.length; i++) {
    result.push(weightSum[i][0])
}
console.log(result.join('\n'))


/*
자 보자.. 그래프 탐색은 해야한다


DFS로 알 수 있는 정보
1. 자식 노드 까지의 거리


부모 노드는 자식 노드가 가진 가중치를 기반으로 자신의 자식 노드들에 대한 거리를 얻는다.


자식 노드는 부모 노드를 통해서 자신의 자식 노드 외의 정보를 얻는다.


각 노드 까지의 가중치를 구하고 더하는 것은 시간이 오버된다. (가중치를 구해두는 것에)
 */