[코딩 인터뷰][LeetCode] – Evaluate Division

Posted on by

※ 이 포스트는 LeetCode의 코딩 인터뷰 문제 Evaluate Division에 대한 풀이입니다. 해당 풀이는 Optimal을 보장하지 않습니다.

문제 정보

문제 출처 : https://leetcode.com/problems/evaluate-division/
카테고리 : Graph, BFS
난이도 : 쉬움 ~ 중간

문제 설명

equations, values, queries가 주어질 때 다음을 리턴하시오.
equations은 리스트로 변수명의 쌍이 멤버로 주어진다. (예 : [ [“a”, “b”], [“b”, “c”] ])
이들이 나타내는 표현식은 a/b, b/c이다.

values는 equations의 표현식의 결과값을 가지고 있다.
예를 들어 values가 [2.0, 3.0]이라면, a/b = 2.0이고 b/c = 3.0이다.

queries는 리스트로 변수명의 쌍이 멤버로 주어진다. queries의 각 멤버 query에 대해
query[0] / query[1]을 출력해야한다. 예를 들어 queries가 [ [“a”, “b”], [“b”, “c”] ]) 이면 2.0, 3.0이 출력된다.
[“b”, “a”]에 대해선 0.5를 출력할 수 있겠다. 만약 값을 모른다면 -1.0을 출력한다.

문제 풀이

equations와 values로 초기 그래프를 구성할 수 있다. 예를 들어 위 자료에서는 노드 a에서 b로 향하는 가중치 2.0의 간선이 존재한다. 반대로 b에서 a로 향하는 0.5의 간선이 존재한다. 자기자신에 대해서는 1의 간선이 존재한다.

모든 정점에 대해 자신으로부터 도달할 수 있는 모든 노드를 찾고 graph를 업데이트한다. graph[src][dest]는 src/dest의 값을 가리킨다. src에서 출발해서 현재 cur에 도달한 상태에서, 다음 노드 next를 탐색한다고 가정하자.
graph[src][next] = graph[src][cur] * graph[cur][next]가 된다.

이 탐색이 끝난 후에 각 query에 대해서 graph[src][dest]를 출력하고 만약 매핑이 되어있지 않다면 -1.0을 출력한다.

코드
class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        graph = {}
        for (equation, value) in zip(equations, values):
            src, dest = equation[0], equation[1]
            if src not in graph:
                graph[src] = {}
            if dest not in graph:
                graph[dest] = {}
            graph[src][dest] = value
            graph[src][src] = 1.0
            graph[dest][src] = float(1.0) / value
            graph[dest][dest] = 1.0
        
        answer = []
        for src in graph.keys():
            visited = {src}
            q = [src]
            while len(q) > 0:
                cur = q[0]
                del q[0]
                for next_node in graph[cur].keys():
                    if next_node not in visited:
                        visited.add(next_node)
                        q.append(next_node)
                        graph[src][next_node] = graph[src][cur] * graph[cur][next_node]
                        
        for query in queries:
            src, dest = query[0], query[1]
            if src not in graph or dest not in graph[src]:
                answer.append(-1.0)
            else:
                answer.append(graph[src][dest])
        return answer