Keys and Rooms

Problem Description

• The keys and rooms problem provides you with n number of rooms, each labelled from 0 to n-1. It is states that all the rooms except for room 0 are locked, and behind each room is a set of distinct keys. Each has a number on it denoting which room it opens.
• So, given an array called rooms where rooms[i] is the set of keys you find in each of the locked rooms (represented by the index of the value in the array, which in other words is the number of the room to be open), we are tasked with finding out if all the rooms can be opened from each of the keys we find from each room.
• We simply return true if possible and false if not. Here is an example of what the input would look like:

rooms = [[1],[2],[3],[]]
# Each index represents a room, and each sub-list represents the array
# of keys behind that room

Solution Explanation

• As a solution to this problem, we can utilize a depth first search based solution where we implement a stack to mark all the visited rooms and then setup an algorithm that goes deep into each room it can open and proceeds from there. Take the following diagram for example:
  
• Given that room 2 is not reachable, we end up having to state that not all the rooms are openable. This is a conclusion we come to when we find out that not all the rooms have been explored given that the len(visited_set) != len(rooms) thereafter helping us determine how to find out if something has been found or not.
• The reason we are using a DFS is because we want to go into depth with each key we find inside each room and then proceed to unlock whatever other rooms that can be unlocked from them. Once we come across a room that either has no keys or only keys to rooms we already visited, then we backtrack to the last value we did not explore. Take this as another example:
  
• Here, the len(rooms) = len(visited) so from this we may denote that all the rooms can be visited given that they were all unlocked and explored. So, utilizing a DFS would prove to be the most ideal solution here. Refer to the implementation below:

Implementation

• This is an iterative depth first search:

class Solution:

    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:

        visited = set() # start by initalizing a visited set

        stack = [0]                    # start in room 0

        while stack:

            room = stack.pop() # popped element here is the room we're in

            if room in visited:

                continue

            visited.add(room)

            for key in rooms[room]:    # each key opens another room

                if key not in visited:

                    stack.append(key)

        return len(visited) == len(rooms)

• This is a recursive depth first search:

class Solution:
	def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
		seen = set()
		seen.add(0)
		
		def dfs(room):
			for key in rooms[room]:
				if key in seen:
					continue
				seen.add(key)
				dfs(key) # we initalize the recursive search here
		dfs(0)
		return len(seen) == len(rooms)