- Problem

399. Evaluate Division

- 내 풀이 (BFS)

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        def bfs(start, end):
            q = deque([(1.0, start)])
            seen = {start}

            while q:
                cur_cost, cur_node = q.popleft()
                
                if cur_node == end:
                    return cur_cost

                for nei_cost, nei_node in graph[cur_node]:
                    if nei_node not in seen:
                        seen.add(nei_node)
                        q.append((cur_cost * nei_cost, nei_node))

            return -1.0

        graph = defaultdict(list)

        for (u, v), value in zip(equations, values):
            graph[u].append([value, v])
            graph[v].append([value ** -1, u])
        
        return [bfs(u, v) if u in graph and v in graph else -1.0 for u, v in queries]

- 결과