ข้อ 46 · LC399 Evaluate Division (คำนวณการหาร) 🟡

โจทย์ (LC399): กำหนด array ของคู่ตัวแปร equations และ array ของจำนวนจริง values โดย equations[i] = [Ai, Bi] และ values[i] แทนสมการ Ai / Bi = values[i] กำหนด queries มาด้วย โดย queries[j] = [Cj, Dj] แทนคำถามที่ j ว่า Cj / Dj มีค่าเท่าไร ให้ return คำตอบของทุก query ถ้า query ไหนหาคำตอบไม่ได้ (ตัวแปรไม่รู้จัก หรือไม่เชื่อมถึงกัน) ให้ตอบ -1.0 สำหรับ query นั้น

แนวทาง — ต้องใช้อะไร & คิดยังไง

ใช้ DFS บน weighted graph (กราฟถ่วงน้ำหนัก) คือ edge (เส้นเชื่อม) มีตัวเลขกำกับ ไอเดียคือแต่ละตัวแปรเป็น node (โหนด) สมการ a/b = 2.0 บอกว่าจาก a เดินไป b คูณ 2.0 และเพราะ b/a เท่ากับ 1/(a/b) เราจึงเพิ่ม edge ย้อนกลับจาก b ไป a คูณ 1/2.0 ด้วย ทำให้เดินได้สองทาง

การหาคำตอบ x/y คือ traverse (เดินไล่) จาก x ไป y แล้วคูณ weight (น้ำหนัก) ของ edge ที่ผ่านทั้งหมดสะสมกันไป DFS ที่นี่ต่างจากข้อก่อน ๆ ตรงที่มันต้อง return (คืนค่า) ผลคูณสะสมกลับขึ้นมา ไม่ใช่แค่ mark เมื่อเดินไปเจอ dst เราคืน 1.0 แล้วระหว่างถอย recursion (การเรียกตัวเอง) กลับ แต่ละชั้นคูณ weight ของ edge ตัวเองเข้าไป

1. สร้าง graph graph[a][b] = val และ graph[b][a] = 1/val สำหรับทุกสมการ
2. เขียน dfs(src, dst, visited) ถ้า src หรือ dst ไม่มีใน graph คืน -1.0 (ไม่รู้จัก)
3. ถ้า src == dst คืน 1.0 (เจอปลายทางแล้ว หรือ x/x)
4. mark src แล้ว iterate (วน) เพื่อนบ้าน (neighbor) (nbr, weight) ที่ยังไม่ visited
5. เรียก dfs(nbr, dst) ถ้าผลไม่ใช่ -1.0 (มีทางถึง) คืน weight × result
6. ถ้าลองทุกทางแล้วไปไม่ถึง คืน -1.0 ทำ dfs แยกทีละ query

from collections import defaultdict

def calc_equation(equations, values, queries):
    graph = defaultdict(dict)
    for (a, b), val in zip(equations, values):
        graph[a][b] = val          # a/b = val
        graph[b][a] = 1 / val      # b/a = 1/val

    def dfs(src, dst, visited):
        if src not in graph or dst not in graph:
            return -1.0            # มีตัวแปรที่ไม่รู้จัก
        if src == dst:
            return 1.0             # x/x = 1 (ต้องรู้จัก x ด้วย)
        visited.add(src)
        for nbr, weight in graph[src].items():
            if nbr not in visited:
                result = dfs(nbr, dst, visited)
                if result != -1.0:        # เจอทางถึง dst
                    return weight * result  # คูณน้ำหนักสะสม
        return -1.0                # ลองทุกทางแล้วไปไม่ถึง

    answers = []
    for a, b in queries:
        answers.append(dfs(a, b, set()))
    return answers

eq = [["a", "b"], ["b", "c"]]
vals = [2.0, 3.0]
q = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
print(calc_equation(eq, vals, q))  # [6.0, 0.5, -1.0, 1.0, -1.0]

[6.0, 0.5, -1.0, 1.0, -1.0]