399. Evaluate Division

[zeikar]

Problem link

https://leetcode.com/problems/evaluate-division/

Problem Summary

방정식과 결과 값이 주어질 때 방정식을 받아서 값을 계산하는 문제.

Solution

체인 형태로 연결되어 있는 것이 그래프가 생각났다.

a / c = (a / b) * (b / c)

위 식이 핵심인데, a - b - c 를 죽 이었을 때 a / c 의 답을 얻을 수 있다.

a -> b 의 간선은 a / b 의 값으로, b -> a 의 간선은 1 / (a / b) 로 값을 세팅한 후 쿼리가 오면 경로대로 곱해주면 답이다.
BFS 탐색으로 시작부터 끝까지 돌면서 나오는 값들을 다 곱해주었다. 예외 처리로 없는 값이 들어오는 것만 처리해주면 쉽게 풀린다.

Source Code

import math
from collections import defaultdict, deque
from typing import List


class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        edges = defaultdict(list)

        for i in range(len(equations)):
            (a, b) = equations[i]
            edges[a].append((b, values[i]))
            edges[b].append((a, 1.0 / values[i]))

        def bfs(node, target):
            if len(edges[node]) == 0:
                return math.inf

            visited = defaultdict(bool)
            queue = deque([(node, 1.0)])
            visited[node] = True

            while queue:
                (current, value) = queue.popleft()

                if current == target:
                    return value

                for (next, mul) in edges[current]:
                    if visited[next]:
                        continue

                    queue.append((next, value * mul))
                    visited[next] = True

            return math.inf

        res = []
        for query in queries:
            result = bfs(query[0], query[1])
            res.append(result if result != math.inf else -1.0)

        return res