[LeetCode] 399. Evaluate Division

😎풀이

1. graph를 생성하여 서로의 가중치 저장
2. queries 순회
   2-1. C에서 D를 통하는 가중치를 DFS 형식으로 곱한 결괏값 배열에 추가
3. 결괏값 배열 반환

type Node = {
    key: string
    multiply: number
}

function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
    const graph = new Map<string, Node[]>()
    const len = equations.length
    for(let i = 0; i < len; i++) {
        const [parent, child] = equations[i]
        const multiply = values[i]
        graph.set(parent, [...(graph.get(parent) ?? []), { key: child, multiply }])
        graph.set(child, [...(graph.get(child) ?? []), { key: parent, multiply: 1 / multiply }])
    }
    function getMultiply(curr: string, target: string, visited: Set<string>) {
        if(!graph.has(curr) || !graph.has(target)) return -1
        if(curr === target) return 1
        visited.add(curr)
        const children = graph.get(curr)
        for(const { key, multiply } of children) {
            if(visited.has(key)) continue
            const res = getMultiply(key, target, visited)
            if(res === -1) continue
            return res * multiply
        }
        return -1
    }
    const calc = []
    for(const [C, D] of queries) {
        const multiply = getMultiply(C, D, new Set())
        calc.push(multiply)
    }
    return calc
};