LeetCode - 399. Evaluate Division (JavaScript)

Medium, DFS

RunTime : 0 ms / Memory : 49.31 MB

문제

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

풀이

• 먼저 equations에 등장하지 않은 인자들을 찾기위해 totalSet을 구성했다.
• 이후에, 각 수식에 대해 a -> b의 weight로 values[i]를, b -> a의 weight로 1/values[i]를 갖는 그래프를 구성했다.
• 후에는 queries를 탐색하며 totalSet에 없는 인자가 있다면 바로 -1을,
  둘다 있다면, dfs를 수행해 값을 찾는다.

var calcEquation = function(equations, values, queries) {
    let totalSet = new Set();
    let graph = new Map();

    for(let i = 0; i < equations.length; i++){
        let [a, b] = equations[i];
        totalSet.add(a);
        totalSet.add(b);

        // 각 노드에 연결된 노드와 가중치를 배열로 추가
        if (!graph.has(a)) graph.set(a, []);
        if (!graph.has(b)) graph.set(b, []);

        graph.get(a).push([b, values[i]]);
        graph.get(b).push([a, 1 / values[i]]);
    }

    const dfs = (node, e, val, visited) => {
        if(node === e){
            return val;
        }

        visited.add(node);

        for(let [v, w] of graph.get(node)){
            if(!visited.has(v)){
                const tmp = dfs(v, e, val * w, visited);
                if(tmp !== -1){
                    return tmp;
                }
            }
        }
        visited.delete(node);
        return -1;
    }

    const n = queries.length;
    let res = Array(n).fill(0.0);

    for(let i = 0; i < n; i++){
        let [a, b] = queries[i];
        if(!totalSet.has(a) || !totalSet.has(b)){
            res[i] = -1.00000;
            continue
        } else {
            let visited = new Set();
            res[i] = dfs(a, b, 1, visited);
        }
    }
    return res;
};