Program to check whether we can unlock all rooms or not in python

Suppose we have a list of lists called rooms. Each index i in rooms represents a room and rooms[i] represents different keys to open other rooms. The room 0 is open and we are at that room and every other room is locked. We can move freely between opened rooms; we have to check whether we can open every room or not.

So, if the input is like rooms = [[2, 0], [3],[1],[]], then the output will be True, as we start from room 0 and can go to room 2 with its key 2. From room 2 we can go to room 1. Then, take the key for room 3 and open it. So all are opened.

To solve this, we will follow these steps:

• n := size of rooms
• ready := a list with single element 0
• seen := a new set
• while ready is not empty, do
  • u := last element of ready and delete it from ready
  • mark u as seen
  • for each v in rooms[u], do
    • if v is not seen, then
      • insert v at the end of ready
• return true when size of seen is same as n, otherwise false.

Let us see the following implementation to get better understanding:

Example

Live Demo

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))

Input

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

Output

True