[LeetCode] 399. Evaluate Division, Medium

1. 문제

• equitions에 문자열 2차원 배열이 주어지고, 각 문자열을 나눈 값을 담은 배열 values가 주어질 때, queries의 나눈 값을 담은 배열을 반환하라.
• 존재할 수 없는 경우는 -1.0을 담아야 한다.

2. 해결

function calcEquation(
    equations: string[][],
    values: number[],
    queries: string[][]
): number[] {
    const graph = new Map<string, [string, number][]>();

    // 그래프 만들기
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        const value = values[i];

        if (!graph.has(a)) graph.set(a, []);
        if (!graph.has(b)) graph.set(b, []);

        graph.get(a)!.push([b, value]);     // a -> b (value)
        graph.get(b)!.push([a, 1 / value]); // b -> a (1/value)
    }

    // DFS 함수
    const dfs = (
        current: string,
        target: string,
        visited: Set<string>,
        acc: number
    ): number => {
        if (!graph.has(current) || !graph.has(target)) return -1.0;
        if (current === target) return acc;

        visited.add(current);

        for (const [neighbor, value] of graph.get(current)!) {
            if (!visited.has(neighbor)) {
                const result = dfs(neighbor, target, visited, acc * value);
                if (result !== -1.0) return result;
            }
        }

        return -1.0;
    };

    // 쿼리 처리
    const results: number[] = [];

    for (const [a, b] of queries) {
        const visited = new Set<string>();
        results.push(dfs(a, b, visited, 1));
    }

    return results;
}

• 못풀었다.
• 원리는 각 문자열의 비율을 이용해 역수를 구하여 map에 저장하여 그래프 형태로 만든다.
  • a/b = 2.0이면 b/a = 1/2.0이 된다.
• queries의 문자열을 탐색하면서, 그래프를 DFS 탐색해 구한다. a/c의 경우 a/b * b/c를 통해 구할 수 있다.