Задача Ключи и комнаты

Сложность: Средняя

Условие: Даны n комнат проиндексированных с 0, все они закрыты кроме комнаты с номером 0. Необходимо посетить все комнаты, однако этого нельзя сдеать не имея ключа от соответствующей закрытой двери. 

При посещении какой-либо комнаты в ней находится определенная связка уникальных ключей, номер ключа означет номер комнаты, для которой он отпирает дверь. Можно использовать сразу все связку ключей. 

На вход подается массив комнат, где в i-ячейке дан список ключей, находящихся в текущей комнате. Необходимо определеть, можно ли обойти все комнаты. 

Пример:

Ввод: rooms = [[1],[2],[3],[]]

Вывод: true

Объяснение: из 0 комнаты можно попасть в 1, из 1 во 2, из 2 в 3. 

Ввод: rooms = [[1,3],[3,0,1],[2],[0]]

Вывод: false

Решение

from collections import deque, defaultdict

class Solution:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:

q = deque(rooms[0]) #deque -> doubly ended queue

visited = defaultdict(int)

visited[0]=1

count = 1 #to keep a count of unique number of rooms visited

while q:

room = q.popleft() #poping first element

if room not in visited:

visited[room] = 1

count+=1

q+=rooms[room]

if count==len(rooms):

return True

return False

```