โปรแกรมตรวจสอบว่าสามารถเปิดห้องทั้งหมดได้หรือไม่ใน Python

มี rooms รายการกุญแจในแต่ละห้อง ห้อง 0 เปิดอยู่ ตรวจสอบว่าเดินไปเปิดห้องอื่นได้หมดหรือไม่

เช่น rooms=[[2,0],[3],[1],[]] ให้ True (0→2→1→3)

ขั้นตอนการแก้ปัญหา

• DFS/BFS จากห้อง 0: เก็บ ready ห้องที่จะไป, seen ห้องที่ไปแล้ว
• Pop ห้องจาก ready, เพิ่มกุญแจที่ยังไม่ได้ไปเข้า ready
• ท้ายสุดถ้า len(seen) == n คืน True

ตัวอย่างโค้ด

class Solution:
    def solve(self, rooms):
        n = len(rooms)
        ready = [0]
        seen = set()
        while ready:
            u = ready.pop()
            seen.add(u)
            for v in rooms[u]:
                if v not in seen:
                    ready.append(v)
        return len(seen) == n

ob = Solution()
rooms = [[2,0],[3],[1],[]]
print(ob.solve(rooms))

อินพุต

rooms = [[2,0],[3],[1],[]]

เอาต์พุต

True