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