ข้อ 43 · LC841 Keys and Rooms (กุญแจกับห้อง) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

มองห้องเป็น node กุญแจเป็น edge ทำ DFS จากห้อง 0 แล้วเช็คว่า visited ครบทุกห้องไหม

โจทย์ (LC841): มี n ห้องเลข 0 ถึง n-1 ทุกห้องล็อกอยู่ ยกเว้นห้อง 0 เป้าหมายคือเข้าให้ครบทุกห้อง แต่ห้ามเข้าห้องที่ล็อกโดยไม่มีกุญแจ เมื่อเข้าห้องใดห้องหนึ่งแล้วอาจพบกุญแจชุดหนึ่งอยู่ในห้องนั้น กุญแจแต่ละดอกมีเลขกำกับว่าไขห้องไหนได้ และหยิบเก็บไปใช้เปิดห้องอื่นต่อได้ กำหนด array rooms โดย rooms[i] คือชุดกุญแจที่จะได้ถ้าเข้าห้อง i ให้ return true ถ้าสามารถเข้าได้ครบทุกห้อง ไม่งั้น return false

Example 1

Input:: rooms = [[1],[2],[3],[]]
Output:: true
Explanation:: เริ่มห้อง 0 หยิบกุญแจ 1 ไปเปิดห้อง 1 หยิบกุญแจ 2 ไปเปิดห้อง 2 หยิบกุญแจ 3 ไปเปิดห้อง 3 — เข้าครบทุกห้อง

Example 2

Input:: rooms = [[1,3],[3,0,1],[2],[0]]
Output:: false
Explanation:: ไม่มีกุญแจห้อง 2 อยู่ในห้องใดที่เข้าถึงได้เลย จึงไม่สามารถเข้าห้อง 2 ได้

Constraints (ข้อจำกัด)

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= ผลรวมความยาวของ rooms[i] ทั้งหมด <= 3000
0 <= rooms[i][j] < n
ค่ากุญแจใน rooms[i] แต่ละห้องไม่ซ้ำกัน

rooms เป็น adjacency list (ลิสต์เพื่อนบ้าน) ของ directed graph (กราฟมีทิศ) อยู่แล้ว ไม่ต้องแปลงอะไร

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

ใช้ DFS บน directed graph (กราฟมีทิศ) มองห้องเป็น node (โหนด) และกุญแจในห้องเป็น edge (เส้นเชื่อม) ที่ชี้ไปยังห้องที่มันเปิดได้ โจทย์นี้จริง ๆ คือการถามว่า graph เชื่อมถึงกันหมดจากจุดเริ่มไหม (reachability) เลือก DFS เพราะเราแค่ต้อง traverse (เดินไล่) ให้ทั่วทุกที่ที่ไปถึงได้ ไม่ได้สนใจระยะทาง

ไอเดียคือ DFS จากห้อง 0 เก็บทุกห้องที่ไปถึงลง set visited (เคยเยือน) แล้วสุดท้าย compare (เทียบ) จำนวนห้องที่ visited ได้กับจำนวนห้องทั้งหมด ถ้าเท่ากันแปลว่าเข้าครบ

สร้าง set visited ว่าง ๆ ไว้จำห้องที่เข้าแล้ว
เขียนฟังก์ชัน dfs(room) ที่ mark room ลง visited
ในนั้น iterate (วน) กุญแจทุกดอกในห้องนี้ ถ้ากุญแจชี้ไปห้องที่ยังไม่ visited ให้ dfs เข้าไปต่อ
เรียก dfs(0) เพื่อเริ่มจากห้อง 0
คืนผลว่าจำนวนห้องใน visited เท่ากับจำนวนห้องทั้งหมด (len(rooms)) หรือไม่

จุดพลาดที่พบบ่อย

ลืมเช็ค if key not in visited ก่อนเรียก dfs ทำให้ recursion (การเรียกตัวเอง) วนไม่จบเมื่อกุญแจชี้วนกลับกัน (บางห้องมีกุญแจชี้กลับไปห้องเดิม)

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def can_visit_all_rooms(rooms):
    visited = set()

    def dfs(room):
        visited.add(room)              # เข้าห้องนี้แล้ว
        for key in rooms[room]:        # กุญแจแต่ละดอกในห้องนี้
            if key not in visited:     # ถ้ายังไม่เคยเข้าห้องนั้น
                dfs(key)               # เข้าไปเลย

    dfs(0)                             # เริ่มจากห้อง 0
    return len(visited) == len(rooms)  # เข้าครบทุกห้องไหม

print(can_visit_all_rooms([[1], [2], [3], []]))          # True
print(can_visit_all_rooms([[1, 3], [3, 0, 1], [2], [0]]))  # False

Output

True
False

โจทย์นี้จริง ๆ คือการถามว่า graph เชื่อมถึงกันหมดจากจุดเริ่มไหม (reachability) เรามองห้องเป็น node และกุญแจในห้องเป็น edge แบบ directed ที่ชี้ไปยังห้องที่มันเปิดได้ rooms เองก็เป็น adjacency list อยู่แล้ว ไม่ต้องแปลงอะไร ทำ DFS จากห้อง 0 เก็บทุกห้องที่ไปถึงลง visited แล้วสุดท้าย compare จำนวนห้องที่ visited กับจำนวนห้องทั้งหมด

set visited ทำสองหน้าที่พร้อมกัน ทั้งกันเดินวนซ้ำ และใช้ count (นับ) จำนวนห้องที่เข้าได้ ถ้าไม่มีการเช็ค visited โปรแกรมจะ error จาก recursion ลึกไม่จบเมื่อกุญแจชี้วนกัน

Time O(V + E) traverse ทุก node หนึ่งครั้งและไล่ทุก edge หนึ่งครั้ง V คือจำนวนห้อง E คือจำนวนกุญแจทั้งหมด · Space O(V) จาก visited และความลึกของ call stack

💡 สรุป pattern

โจทย์แนว เข้าถึงทุกจุดจากจุดเริ่มไหม / เชื่อมกันหมดไหม คือ reachability ยิง DFS จากจุดเริ่ม เก็บ visited แล้ว compare จำนวนที่ visited ได้กับจำนวนทั้งหมด