link: https://leetcode.com/problems/keys-and-rooms/

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

🧠 Example to Understand

Input:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
    We visit room 0 and pick up key 1.
    We then visit room 1 and pick up key 2.
    We then visit room 2 and pick up key 3.
    We then visit room 3.
    Since we were able to visit every room, we return true.

Steps

1. Enter Room 0 → get Key 1
2. Enter Room 1 → get Key 2
3. Enter Room 2 → get Key 3
4. Enter Room 3 (no keys, but that’s okay)

We visited every room → ✅ Output: true

Input:

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Steps

1. Enter Room 0 → get Key 1 and Key 3
2. Enter Room 1 → get Key 3, Key 0, Key 1 (we already have these)
3. Enter Room 3 (no keys)

✅ Approach 1: BFS Solution (Queue Exploration)

def canVisitAllRooms(rooms):
    visited = set()
    queue = [0]  # Start with room 0

    while queue:
        room = queue.pop(0)
        if room not in visited:
            visited.add(room)
            for key in rooms[room]:
                queue.append(key)

    return len(visited) == len(rooms)

How it Works

• We explore rooms gradually.
• Every time we enter a room, we pick up all its keys.
• We keep unlocking rooms until no new rooms can be opened.

✅ Approach 2: DFS Solution (Recursive Exploration)

DFS is another way to explore connected rooms — we go deep into rooms as soon as we get keys.

def canVisitAllRooms(rooms):
    visited = set()

    def dfs(room):
        if room in visited:
            return
        visited.add(room)
        for key in rooms[room]:
            dfs(key)

    dfs(0)  # Start from room 0

    return len(visited) == len(rooms)

How DFS Works

• Start in Room 0
• Recursively visit every room whose key we find
• Stop when there are no more new rooms to unlock

🧮 Complexity Analysis

Both solutions are efficient and acceptable.