Leetcode: 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.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.

 

Example 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: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

수학적으로 계산해야 할 것처럼 보이지만, 그래프 문제이다. BFS 혹은 DFS / Union Find로 문제를 풀 수 있다. 

 

BFS

a/b = 2를 'b -> a 사이에 단방향 edge가 있고, 그 weight이 2이다'라고 재정의할 수 있다. 이 때, b/a = 2이면 a/b=1/2로 a->b의 weight과 b->a의 weight은 같을 수 없으므로 이 graph는 단방향 그래프이다. Example1에서 equations에 주어진 edge (x,y,v)에 대해서, weight이 v인 edge y->x, weight이 1/v인 edge x->y를 추가하면, 최종적으로는 equations의 갯수 * 2만큼의 edge가 존재하게 된다. 

그림1: Example1의 예제로 만든 unidirectional graph

이 때, queries에 있는 (x, y)를 구하는 방법은 y -> x 까지 도달하면서 만난 weight의 곱을 구하는 것이 된다. 

예를 들어, ["a","c"]의 경우 (c->b = 3) * (b->a = 2) = 6이며, ["b", "a"]의 경우 1/2이다. ["a", "a"]의 경우 시작 지점과 끝지점이 같으므로 1이 된다. ["a", "e"]나 ["x", "x"]와 같이 그래프에 있지 않은 정점이 주어진 경우, -1을 리턴한다. 

전체 코드는 아래와 같다. 

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)):
            x, y = equations[i]
            edges[y].append((x, values[i]))
            edges[x].append((y, 1/values[i]))

        def calc(a, b) -> float:
            if a not in edges or b not in edges: return -1

            visited = set()
            q = deque([(b, 1)])
            while q:
                x, dist = q.popleft()
                visited.add(x)
                if x == a: return dist
                for y, v in edges[x]:
                    if y not in visited:
                        q.append((y, dist * v))
            return -1

        return [calc(x, y) for x, y in queries]

비슷한 방식으로 DFS를 통해서도 풀 수 있다. 

 

Union Find

Example1처럼 a/b=2,  b/c=3 인 경우, a/c 는 (a/b) * (b/c) 와 같은 방식으로 구할 수 있다. 다만, 이를 조금만 바꿔서 생각해보면, a/c = (c/X) / (a/X) 이고, 이 사이에 끼어있는 X값은 반드시 b일 필요는 없고, 우리가 equations를 통해 알 수 있는 어떠한 값이기만 하면 된다. 그렇다면 문제는, a와 c사이의 X값을 찾을 수 있는지로 귀결되고, 이는 a와 c가 같은 disjoint set에 있는지를 확인함으로써 알 수 있으므로, union find로 문제를 해결한다.

 

이 풀이에서도 a/b = 2 를 union(a,b,2)에 대입시키고, 이는 'b -> a 사이에 단방향 edge가 있고, 그 weight이 2이다'라고 재정의한다. 이를 union find과정에서 parent[b] = (a, 2) 와 같이 표현한다. 

추후에 각 equation을 살펴볼 때마다, 해당 dividend, divisor의 조상 노드를 찾아 union find를 진행하면서, 해당 node에서 조상 노드까지의 weight의 곱을 별도로 저장해둔다. find(X)는 recursive하게 X부터 X의 조상노드까지의 weight의 곱 = expression(rootX/X)을 return한다. 

$$ a / b = v \iff union(a, b, v)$$

$$ find(X) = expression(\frac{rootX}{X})$$

이 경우, X/Y=v라는 식을 바탕으로 union(X, Y, v)을 할 때, find(X) = rootX/X, find(Y) = rootY/Y이므로, find(X)/find(Y) = Y/X * (rootX/rootY)가 된다. 이를 통해, rootX/rootY = find(X)/find(Y) * X/Y = (find(X)/find(Y)) * v = V 임을 도출해낼 수 있고, 이것이 의미하는 바는 union(rootX, rootY, V)가 되므로, rootY->rootX로 weight=find(X)/find(Y) * v 인 단방향 edge가 있다는 의미가 된다. 이런 식으로 X, Y를 바로 연결하기보다는, X와 Y의 root 노드를 찾아서 그 root 노드끼리 연결한다. 

 

$$ \frac{find(X)}{find(Y)} = \frac{rootX}{X} \div \frac{rootY}{Y}$$

$$ \frac{rootX}{rootY} = \frac{find(X)}{find(Y)} * \frac{X}{Y} = \frac{find(X)}{find(Y)} * v = V \iff union(rootX, rootY, V)$$

 

이런 식으로 모든 equations에 대해 union을 하고 나면, queries에 있는 X/Y의 값을 찾을 수 있을 수 있는지 없는지 X와 Y의 조상 노드를 확인하여 알 수 있다. 두 노드의 조상 노드가 동일하다면 (같은 disjoint set에 있다면), (root/Y) / (root/X) = X/Y이므로, X/Y = find(Y) / find(X)가 된다. 두 노드의 조상 노드가 동일하지 않다면 다른 disjoint set에 있으므로 해당 expression을 계산할 방법이 없기 때문에 -1을 return한다. 

$$ rootX = rootY \iff \frac{find(Y)}{find(X)} = \frac{rootY}{Y} \div \frac{rootX}{X} = \frac{root}{Y} \div \frac{root}{X} = X / Y $$

 

Union Find에서 tree의 height를 줄이기 위한 방법인 Union by Rank와 Path Compression도 사용가능하다.

1. Union by Rank: union(X, Y, v) = union(Y, X, 1/v)임을 이용한다. 

2. Path Compression: Path compression시 root까지의 weight도 같이 계산하여 업데이트해준다. 

 

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = defaultdict(int)

    def union(self, x, y, v):
        if x not in self.parent: self.parent[x] = (x, 1)
        if y not in self.parent: self.parent[y] = (y, 1)

        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px[0]] >= self.rank[py[0]]:
            self.parent[py[0]] = (px[0], px[1]/py[1]*v)
            if self.rank[px[0]] == self.rank[py[0]]:
                self.rank[px[0]] += 1
        else:
            self.parent[px[0]] = (py[0], 1 / (px[1]/py[1]*v))

    def find(self, x):  # return (rootX, rootX/x)
        if x != self.parent[x][0]:
            px, v = self.parent[x]
            new_px, new_v = self.find(px)
            self.parent[x] = (new_px, new_v * v)
        return self.parent[x]

    def div(self, x, y):
        if x not in self.parent or y not in self.parent: return -1

        px, py = self.find(x), self.find(y)
        if px[0] != py[0]: return -1
        else: return py[1] / px[1]


class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        uf = UnionFind()
        for i in range(len(equations)):
            x, y = equations[i]
            uf.union(x, y, values[i])

        return [uf.div(x, y) for x, y in queries]

 

 

 

링크: leetcode.com/problems/evaluate-division/

Evaluate Division - LeetCode