Leetcode 399. Evaluate Division

문제

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.

두 변수의 쌍의 배열인 equations 와 배열 한 쌍 (a, b) 에 대해 a / b 의 값을 가지는 equations 배열이 있다.
두 배열을 이용해 queries 배열 내 변수 쌍의 나눗셈 결과를 배열로 리턴하시오.
만약 나눗셈이 불가능하다면 -1을 리턴하시오.

예시

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
a/b 는 2.0이고, b/c 는 3.0 이다.
[6.0, 0.5, -1.0, 1.0, -1.0] 가 쿼리의 결과가 된다.
x는 등장한 적이 없기에 그냥 -1.0 이 된다.

제한

• $1 <= equations.length <= 20$
• $equations[i].length == 2$
• $1 <= A_i.length, B_i.length <= 5$
• $values.length == equations.length$
• $0.0 < values[i] <= 20.0$
• $1 <= queries.length <= 20$
• $queries[i].length == 2$
• $1 <= C_j.length, D_j.length <= 5$

풀이법

• 이 문제는 그래프를 생각하면 쉽게 풀릴수 있다.
• a / b 와 b / c 의 결과가 주어졌다면 ( a / b ) * ( b / c ) 로 a / c의 결과를 얻을수 있을것이다.
• 이는 곧 a -> b 의 edge weight 을 ( a / b ) 로 두고, b -> c 의 edge weight 을 ( b / c ) 로 둔 뒤 a에서 c로 dfs를 하면서 weight을 곱해
  구할수 있다.
• 참고로 a / b 가 주어졌을때 b / a 는 a / b 결과의 역수 ( reciprocal ) 이다.

from typing import Tuple, Dict, Set

class Node:
    def __init__(self, name: str):
        self.name = name
        self.edges: List[Tuple[float, Node]] = []
    def add_edges(self, to: 'Node', value: float):
        self.edges.append((value, to))

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        self.graph: Dict[str, Node] = {}

        for f, s in equations:
          if f not in self.graph:
            self.graph[f] = Node(f)
          if s not in self.graph:
            self.graph[s] = Node(s)

        for i, (f, s) in enumerate(equations):
            self.graph[f].add_edges(self.graph[s], values[i])
            self.graph[s].add_edges(self.graph[f], 1.0 / values[i])

        self.check: Set[str]

        def dfs(start: str, end: str, value: float = 1.0):
            if start not in self.check:
                return -2
            else:
                self.check.remove(start)

            if start == end:
                return value

            ans = []

            for next_node in self.graph[start].edges:
                ans.append(dfs(next_node[1].name, end, value * next_node[0]))

            return max(ans)


        ans: List[float] = []

        for f, s in queries:
            self.check = set(self.graph.keys())
            ans.append(max(dfs(f, s), -1))

        return ans