[파이썬] LeetCode 399. Evaluate Division 👉🏻 수들 간의 수학적 관계를 그래프로 표현하기

🔗 문제

LeetCode 399. Evaluate Division

👀 접근 방법

수들 간의 수학적 관계는 그래프로 표현할 수 있다.

예를 들어 a / b = 2라 한다면 a를 2로 나누면 b가 되고, b를 1/2로 나누면 a가 된다.

이러한 관계는 아래와 같이 그래프로 표현할 수 있다. 즉 어떤 수가 다른 수가 되기 위해 나눠야 하는 수를 간선의 가중치로 삼는 것이다.

만약 query가 ["a", "c"]로 주어진다면 우리는 a / c = ?에서 ?의 값을 구해야 한다.

이 수식은 a / ? = c로 다시 표현할 수 있는데, 즉 a를 어떤 수로 나눠야 c가 될 수 있는지 구하는 것과 동일한 문제이다.

따라서 그래프 상에서 노드 a에서 c까지 가면서 거치는 간선의 가중치를 구하면 될 것이다.

📝 답안

from collections import defaultdict


class Solution:
    def calcEquation(self, equations, values, queries):
        graph = self.buildGraph(equations, values)
        results = [self.calculatePathWeight(start, end, set(), graph) for start, end in queries]
        return results

    # equations과 values를 바탕으로 그래프 생성
    def buildGraph(self, equations, values):
        # 딕셔너리의 딕셔너리 형태로 그래프 생성
        graph = defaultdict(dict)
        # a / b = 2라면 a-> 2 -> b 그리고 b -> 1/2 -> a
        for (u, v), weight in zip(equations, values):
            graph[u][v] = weight
            graph[v][u] = 1 / weight
        return graph

    # DFS 방식으로 start에서 end까지 가는 경로의 가중치 계산
    def calculatePathWeight(self, start, end, visited, graph):
        if start not in graph:
            return -1.0

        if end in graph[start]:
            return graph[start][end]

        visited.add(start)

        for neighbor, weight in graph[start].items():
            if neighbor not in visited:
                cumulativeWeight = self.calculatePathWeight(neighbor, end, visited, graph)
                if cumulativeWeight != -1.0:
                    return weight * cumulativeWeight

        return -1.0