Abrir todas as salas trancadas
A missão
Problema
Um escape room tem n salas numeradas de 0 a n - 1. A sala 0 está aberta e todas as outras começam trancadas. Dentro da sala i há uma lista de chaves, rooms[i], e uma chave de número j abre a sala j. As chaves podem ser usadas quantas vezes você quiser e em qualquer ordem. Retorne True se você conseguir entrar em todas as salas. Há até 1.000 salas e até 3.000 chaves no total.
Exemplos
Input: rooms = [[1], [2], [3], []]
Output: True
Por quê: a sala 0 tem a chave 1, a sala 1 tem a chave 2, a sala 2 tem a chave 3
Input: rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: False
Por quê: a única chave da sala 2 está trancada dentro da própria sala 2
Input: rooms = [[]]
Output: True
Por quê: edge case: a única sala já está aberta
Dicas
0 / 3
Pense em cada sala como um nó e em cada chave como uma aresta direcionada da sala onde ela está para a sala que ela abre.
Aí a pergunta é se todo nó é alcançável a partir do nó 0.
Rode uma busca em profundidade a partir da sala 0 com uma pilha explícita e um conjunto de visitados. Empilhe a sala de cada chave que você ainda não visitou. No fim, compare o tamanho do conjunto de visitados com n.
- Tempo-alvo
- O(n + k)
- Espaço-alvo
- O(n)
Restrições
- n ≤ 1000 rooms
- ≤ 3000 keys in total
- room 0 starts open
Solução
As salas e as chaves formam um grafo direcionado, com uma aresta da sala i para cada sala cuja chave está na sala i, e uma sala pode ser aberta exatamente quando é alcançável a partir da sala 0. Uma busca em profundidade (DFS) a partir da sala 0 marca toda sala alcançável; uma pilha explícita evita recursão profunda em uma longa cadeia de salas. Cada sala é empilhada (push) no máximo uma vez e cada chave é olhada uma vez, então o tempo é O(n + k) para n salas e k chaves, e o espaço é O(n).
def can_open_all(rooms):
seen = {0}
stack = [0]
while stack:
room = stack.pop()
for key in rooms[room]:
if key not in seen: # a room we have not entered yet
seen.add(key)
stack.append(key)
return len(seen) == len(rooms)
print(can_open_all([[1], [2], [3], []])) # -> True
print(can_open_all([[1, 3], [3, 0, 1], [2], [0]])) # -> False
print(can_open_all([[]])) # -> TrueTravou na ideia, e não no código? Busca em profundidade explica isso.