841. Keys and Rooms

[fockspaces]

follow the normal steps to traverse the room not visited

1. first, we already visited room 1 (keys = rooms[0], visited = {0})
2. take all the unvisited keys to current keys list
3. go through all the keys from the current visited room, then go through next room

BFS version:

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        keys = rooms[0]
        visited = {0}
        while keys:
            num_keys = len(keys)
            for _ in range(num_keys):
                key = keys.pop(0)
                visited.add(key)
                keys.extend([key for key in rooms[key] if key not in visited])
        return len(visited) == len(rooms)

[fockspaces]

for speeding up, we should also consider that the new key from room has already exist in current keys

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        keys = rooms[0]
        visited = {0}
        while keys:
            num_keys = len(keys)
            for _ in range(num_keys):
                key = keys.pop(0)
                visited.add(key)
                keys.extend([key for key in rooms[key] if key not in visited and key not in keys])
        return len(visited) == len(rooms)