# 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

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

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`