Teaching Kids Programming – Graph Traversal Algorithms in DFS or BFS (Unlock Rooms with Keys)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 1:
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.

Example 2:
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.

You are given a two-dimensional list of integers rooms. Each index i in rooms represents a room and rooms[i] represents different keys to unlock other rooms.

You are currently in an unlocked room 0 and every other room is locked. Given you can move freely between unlocked rooms, return whether you can unlock every room.

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in rooms.
Example 1
Input
rooms = [
[1, 3],
[2],
[0],
[]
]
Output
True
Explanation
We start off at room 0 and can go to room 1 with its key. From room 1 we can go to room 2. Then, we can go back to room 0 and go to room 3.

Try thinking of rooms like a node. Each room gives you access to more nodes (possibly zero too).
You can find the connected component. If it’s 1 return true;

Keys and Rooms – (Unlock Rooms)

We can visualize this problem by a Graph where the rooms are vertice, and the keys form edges from current room to the rooms that keys can unlock. Then, we start at Vertex 0 and try to traversal the graph with either Depth First Search or Breadth First Search Algortihm.

Unlike the Trees, in a graph, we have to use a hash set to remember the vertex that we have visited so that we don’t end up in cycles. For trees, we don’t usually have this problem because we can’t visit the parents from the children.

Depth First Search Algorithm in a Graph

We can implement the DFS in recursive manner or we can maintain a stack and implement the DFS in iterative manner.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def solve(self, rooms):
        n = len(rooms)
        seen = set()
        def dfs(curRoom):
            if curRoom in seen:
                return
            seen.add(curRoom)
            for key in rooms[curRoom]:
                dfs(key)
        dfs(0)
        return len(seen) == n

class Solution:
    def solve(self, rooms):
        n = len(rooms)
        seen = set()
        def dfs(curRoom):
            if curRoom in seen:
                return
            seen.add(curRoom)
            for key in rooms[curRoom]:
                dfs(key)
        dfs(0)
        return len(seen) == n

If the graph is connected (all vertex in a graph are connected), then the visited size set should be equal to number of all vertex (rooms).

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = set()
        
        def dfs(curRoom):
            if curRoom in seen:
                return
            seen.add(curRoom)
            for key in rooms[curRoom]:
                dfs(key)
                
        dfs(0)
        return len(seen) == len(rooms)

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = set()
        
        def dfs(curRoom):
            if curRoom in seen:
                return
            seen.add(curRoom)
            for key in rooms[curRoom]:
                dfs(key)
                
        dfs(0)
        return len(seen) == len(rooms)

Breadth First Search Algorithm in a Graph

We use a queue to implement the BFS – and particularly in Python, we use deque to ensure O(1) constant time in append/pop operations from both sides of the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def solve(self, rooms):
        n = len(rooms)
        seen = set()
        q = deque([0])
        while q:
            curRoom = q.popleft()
            if curRoom in seen:
                continue
            seen.add(curRoom)
            for key in rooms[curRoom]:
                q.append(key)
        return len(seen) == n

class Solution:
    def solve(self, rooms):
        n = len(rooms)
        seen = set()
        q = deque([0])
        while q:
            curRoom = q.popleft()
            if curRoom in seen:
                continue
            seen.add(curRoom)
            for key in rooms[curRoom]:
                q.append(key)
        return len(seen) == n

Here is another implementation of BFS Algorithm for the Graph – we always put the starting vertex (initial location) into the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = set()
                
        def bfs(startRoom):
            q = deque([startRoom])
            while q:
                room = q.popleft()
                if room in seen:
                    continue
                seen.add(room)
                for key in rooms[room]:
                    q.append(key)
                
        bfs(0)
        return len(seen) == len(rooms)

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = set()
                
        def bfs(startRoom):
            q = deque([startRoom])
            while q:
                room = q.popleft()
                if room in seen:
                    continue
                seen.add(room)
                for key in rooms[room]:
                    q.append(key)
                
        bfs(0)
        return len(seen) == len(rooms)

See also: Depth First Search and Breadth First Search Algorithm to Open the Doors to the Rooms with Keys

–EOF (The Ultimate Computing & Technology Blog) —