Abrir todas las habitaciones cerradas
La misión
Problema
Un escape room tiene n habitaciones numeradas de 0 a n - 1. La habitación 0 está abierta y todas las demás empiezan cerradas con llave. Dentro de la habitación i hay una lista de llaves, rooms[i], y una llave con el número j abre la habitación j. Las llaves se pueden usar cualquier cantidad de veces y en cualquier orden. Devuelve True si puedes entrar a todas las habitaciones. Hay hasta 1000 habitaciones y hasta 3000 llaves en total.
Ejemplos
Input: rooms = [[1], [2], [3], []]
Output: True
Por qué: la habitación 0 tiene la llave 1, la habitación 1 tiene la llave 2 y la habitación 2 tiene la llave 3
Input: rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: False
Por qué: la única llave de la habitación 2 está encerrada dentro de la propia habitación 2
Input: rooms = [[]]
Output: True
Por qué: caso límite: la única habitación ya está abierta
Pistas
0 / 3
Piensa en cada habitación como un nodo y en cada llave como una arista dirigida desde la habitación donde está hasta la habitación que abre.
Entonces la pregunta es si cada nodo es alcanzable desde el nodo 0.
Haz una búsqueda en profundidad desde la habitación 0 con una pila explícita y un conjunto de visitados. Agrega a la pila la habitación de cada llave que todavía no hayas visitado. Al final, compara el tamaño del conjunto de visitados con n.
- Tiempo objetivo
- O(n + k)
- Espacio objetivo
- O(n)
Restricciones
- n ≤ 1000 rooms
- ≤ 3000 keys in total
- room 0 starts open
Solución
Las habitaciones y las llaves forman un grafo dirigido, con una arista de la habitación i a cada habitación cuya llave está en la habitación i, y se puede entrar a una habitación exactamente cuando es alcanzable desde la habitación 0. Una búsqueda en profundidad (DFS) desde la habitación 0 marca cada habitación alcanzable; una pila (stack) explícita evita una recursión profunda en una cadena larga de habitaciones. Cada habitación se agrega a la pila como máximo una vez y cada llave se revisa una vez, así que el tiempo es O(n + k) para n habitaciones y k llaves, y el espacio es 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([[]])) # -> True¿Lo que te frena es la idea y no el código? Búsqueda en profundidad lo explica.