Sponsored
Sponsored
The idea is to use Depth-First Search (DFS) to explore all reachable rooms starting from room 0. This can be implemented either recursively or iteratively with a stack. We maintain a set of visited rooms and attempt to visit all rooms that we have keys for, recursively adding rooms to the visited set as we access them. The process continues until no new rooms can be explored.
1def canVisitAllRooms(rooms):
2 visited = set()
3
4 def dfs(room):
5 if room not in visited:
6 visited.add(room)
7 for key in rooms[room]:
8 dfs(key)
9
10 dfs(0)
11 return len(visited) == len(rooms)This solution defines a dfs function to explore rooms recursively. The visited set is used to keep track of rooms that have already been visited to avoid re-processing. The algorithm starts DFS from room 0, recursively visiting each room for which we have a key until no new rooms can be visited.
Instead of using DFS, we can also use Breadth-First Search (BFS) to explore the rooms iteratively. We use a queue to maintain the rooms to be visited next. Initially, room 0 is added to the queue. As we visit each room, we add all the keys found in that room to the queue, provided we haven't visited the corresponding rooms yet. This approach ensures a layer-wise exploration similar to BFS.
1
In this Python BFS implementation, we utilize a deque as a queue. Initially, room 0 is added to the queue and visited set. We process each room in the queue by adding unvisited rooms (for which we have keys) to the visited set and queue. We continue this until the queue is empty and then check if all rooms have been visited.