[leetcode] 399. Evaluate Division - 이번에도 Runtime 100%!

안녕하세요. 요즘 leetcode 문제를 열심히 풀고 있습니다.

그래서 알고리즘 문제 풀이를 따로 포스팅 하지 않았습니다만...

 

leetcode의 399. Evaluate Division 문제를 Runtime 100%로 풀게 되어서 포스팅하게 되었습니다.

 

Runtime 100%!!!

 

---

1. 문제

이 문제는 equations, values, queries 파라미터가 주어집니다.

 

equations은 2개의 문자열로 이뤄진 리스트의 리스트로 values와 한 쌍이고

equations[i][0] / equations[i][1] = values[i] 라는 뜻을 가집니다.

• 예시
  • equations = [["a","b"],["b","c"]]
  • values = [2.0, 3.0]
  • a / b = 2.0, b / c = 3.0

queries는 equations와 동일하게 2개의 문자열로 이뤄진 리스트의 리스트인데

values라는 값이 주어지지 않고, 우리가 계산해내야 합니다.

• 예시
  • equations = [["a","b"],["b","c"]]
  • values = [2.0, 3.0]
  • queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
    • a / c = (a / b) * (b / c) = 6.0
    • b / a = 1 / (a / b) = 0.5
    • a / e = -1 (계산 불가)
    • a / a = -1 (계산 불가)
    • x / x = -1 (계산 불가)
  • 정답 = [6.0, 0.5, -1.0,-1.0, -1.0]

2. 풀이

처음에는 주어진 식들을 이용해서 queries의 식들을 만들기 위해서 brute force 방식을 생각했지만 경우의 수가 2^N으로 너무 컸습니다.

 

그래서 다른 방법을 찾던 중 query가 갑자기 start / goal 로 해석되더라고요.

• equation의 각 변수들은 노드
• equation은 node 간의 연결 상태를 알려주는 엣지
• value는 엣지의 weight (반대 방향은 역수)

1에서 예시로 들었던 것을 그래프로 그리면 다음과 같습니다.

equations를 이용해서 만든 그래프

 

a / c는 a에서 c까지 가는데 edge의 weight을 곱한 6.0이고 b / a는 0.5입니다.

그 외의 경우는 경로가 없고 이럴 때는 -1을 반환하면 됩니다.

 

이제 경로 계획 알고리즘 문제가 되었습니다!

경로 상의 edge weight의 합을 구하는 것이 아니라 edge weight의 곱을 구한다는 점에서 조금 다르지만 거의 동일합니다.

 

저는 dijkstra 알고리즘을 이용해서 문제를 풀었습니다.

+ 코드

import  heapq


class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        adjacent_nodes_dict: Dict[str, Dict[str, float]]  = collections.defaultdict(dict)
        for i, [start, end] in enumerate(equations):
            adjacent_nodes_dict[start][end] = values[i]
            adjacent_nodes_dict[end][start] = 1 / values[i]

        answers = []
        for [start, goal] in queries:
            answers.append(self.find_distance_of_path(adjacent_nodes_dict, start, goal))
        return answers
    
    def find_distance_of_path(self, adjacent_nodes_dict: Dict[str, Dict[str, float]], start: str, goal: str) -> float:
        visited: Dict[str, float] = collections.defaultdict(float)
        queue: List[Tuple[float, str]] = []
        for node, weight in adjacent_nodes_dict[start].items():
            heapq.heappush(queue, (weight, node))

        while len(queue) > 0:
            (g_val, node) = heapq.heappop(queue)
            if node == goal:
                return g_val
            visited[node] = g_val
            for (next_node, weight) in adjacent_nodes_dict[node].items():
                if visited[next_node] >= weight * g_val:
                    continue
                heapq.heappush(queue, (weight * g_val, next_node))
        return -1