ข้อ 44 · LC547 Number of Provinces (นับจำนวนจังหวัด) 🟡

โจทย์ (LC547): มี n เมือง บางเมืองเชื่อมกันโดยตรง บางเมืองไม่เชื่อม กำหนด n x n matrix ชื่อ isConnected โดย isConnected[i][j] = 1 หมายถึงเมือง i กับเมือง j เชื่อมกันโดยตรง และ isConnected[i][j] = 0 หมายถึงไม่เชื่อม province คือกลุ่มของเมืองที่เชื่อมถึงกันได้ทั้งทางตรงและทางอ้อม ให้ return จำนวน province ทั้งหมด

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

นี่คือการนับ connected components คือกลุ่มก้อนของ node (โหนด) ที่เชื่อมถึงกันได้ใน undirected graph (กราฟไม่มีทิศ) ใช้ DFS traverse (เดินไล่) กวาดแต่ละกลุ่ม เลือก DFS เพราะเราแค่ต้องกวาดให้ทั่วทั้งกลุ่มเพื่อ mark ว่าเมืองพวกนี้อยู่แคว้นเดียวกันแล้ว

เทคนิคนับกลุ่มคือ iterate (วน) node ทุกตัวจากข้างนอก ถ้าเจอตัวที่ยังไม่ visited (เคยเยือน) แสดงว่าเราเพิ่งสะดุดเข้าแคว้นใหม่ที่ยังไม่เคยแตะ บวกตัวนับหนึ่ง แล้วยิง DFS เข้าไปกวาดทุกเมืองในแคว้นนั้นให้ visited จนหมด พอ loop (วน) นอกเดินต่อ เมืองที่อยู่แคว้นเดิมจะถูก visited แล้วจึงไม่ถูก count (นับ) ซ้ำ

1. อ่านจำนวนเมือง n จากขนาดตาราง แล้วสร้าง set visited
2. เขียน dfs(city) ที่ mark city แล้ว iterate ดูทุกเมือง other ในแถวนั้น
3. ถ้า isConnected[city][other] เป็น 1 และ other ยังไม่ visited ให้ dfs(other) ต่อ
4. ตั้งตัวนับ provinces = 0 แล้ว iterate city ทุกเมืองจากข้างนอก
5. ถ้า city ยังไม่ visited บวก provinces หนึ่ง แล้ว dfs(city) กวาดทั้งแคว้น
6. คืน provinces

ไล่ทีละสเต็ป

รันบน isConnected = [[1,1,0],[1,1,0],[0,0,1]] (loop นอก iterate city 0,1,2)

def find_circle_num(is_connected):
    n = len(is_connected)
    visited = set()

    def dfs(city):
        visited.add(city)
        for other in range(n):
            # เชื่อมกันโดยตรง และยังไม่เคยไป
            if is_connected[city][other] == 1 and other not in visited:
                dfs(other)

    provinces = 0
    for city in range(n):
        if city not in visited:        # เจอเมืองที่ยังไม่อยู่แคว้นไหน
            provinces += 1             # นับเป็นแคว้นใหม่
            dfs(city)                  # กวาดทุกเมืองในแคว้นนี้
    return provinces

print(find_circle_num([[1, 1, 0], [1, 1, 0], [0, 0, 1]]))  # 2
print(find_circle_num([[1, 0, 0], [0, 1, 0], [0, 0, 1]]))  # 3

2
3