---
# System prepended metadata

title: 841. Keys and Rooms
tags: [leetcode]

---

# 841. Keys and Rooms
#### Difficulty: Medium
link: https://leetcode.com/problems/keys-and-rooms/


這題可以看成一個graph，房間是node，房間鑰匙是edge，從0號node出發能否traverse所有的node，BFS和DFS的做法都行。

### 1. BFS  
#### $O(n)$ runtime, $O(n)$ space


##### python
```python=
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set([0])
        queue = deque([0])
        while queue:
            i = queue.popleft()
            for neigh in rooms[i]:
                if neigh not in visited:
                    visited.add(neigh)
                    queue.append(neigh)
        
        return len(visited) == len(rooms)
```

### 2. DFS  
#### $O(n)$ runtime, $O(n)$ space


##### python
```python=
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set([0])
        
        def dfs(i):
            for neigh in rooms[i]:
                if neigh not in visited:
                    visited.add(neigh)
                    dfs(neigh)
        
        dfs(0)
        
        return len(visited) == len(rooms)
```

###### tags: `leetcode`