Cuando un cultivo de naranjas comienza a dañarse, la plaga se propaga día a día hacia las plantas vecinas. Este problema clásico de algoritmos, conocido como rotting oranges, pone a prueba tu capacidad para recorrer estructuras de datos por niveles y determinar en cuántos días todo el cultivo quedará podrido. Entender su solución te prepara para enfrentar problemas similares en entrevistas técnicas y competencias de programación.
¿Cómo se representa el cultivo en una matriz?
El cultivo se modela como una matriz de ceros, unos y dos [0:18]:
- 0: espacio vacío, sin plantas sembradas.
- 1: planta de naranja fresca.
- 2: planta de naranja ya podrida.
El objetivo es retornar la cantidad de días que transcurren hasta que todas las naranjas frescas estén podridas. Cada día, una naranja podrida contagia a sus vecinas en las cuatro direcciones: arriba, abajo, izquierda y derecha. Las diagonales no cuentan como adyacentes en este planteamiento [1:28].
¿Por qué BFS es la estrategia ideal para este problema?
Al observar cómo se propaga la plaga, se nota un patrón claro: desde cada naranja podrida, el daño se extiende nivel por nivel [2:26]. El primer día se pudren las naranjas directamente adyacentes, el segundo día las siguientes, y así sucesivamente. Esto es exactamente lo que hace un recorrido BFS (Breadth-First Search), también llamado recorrido en anchura.
Cada naranja puede verse como un nodo en un grafo, y sus vecinas como nodos conectados. Al recorrer este grafo por niveles, cada nivel equivale a un día. La cantidad total de niveles recorridos es la respuesta al problema [3:56].
¿Cómo se sabe que el proceso terminó?
El recorrido finaliza cuando, al revisar las casillas adyacentes de las últimas naranjas procesadas, ya no existen naranjas frescas por contagiar [4:10]. Si todas las vecinas son ceros o ya están podridas, no hay más trabajo por hacer.
¿Qué estructura de datos se necesita para el recorrido?
Para implementar BFS se utiliza una cola (queue) [4:42]. La cola garantiza que lo primero que entra es lo primero que sale (FIFO), lo cual respeta el orden temporal de la propagación: las naranjas que se pudrieron primero se procesan primero.
Además, es fundamental llevar un registro de las posiciones ya visitadas para no procesar dos veces la misma naranja. Para esto se emplea un hash set [3:22], ya que verificar si un elemento existe dentro de esta estructura tiene una complejidad de O(1). Si se usara un arreglo común, esa verificación sería O(n) porque habría que recorrer todos los elementos almacenados.
¿Cuál es la complejidad de esta solución?
El peor caso ocurre cuando todo el cultivo tiene naranjas frescas y la propagación debe cubrir la matriz completa [5:14]. Si la matriz es de tamaño n × n, la complejidad temporal es O(n²), ya que cada celda se visita como máximo una vez.
La complejidad espacial también depende del tamaño de la matriz, considerando la cola y el hash set que almacenan las posiciones.
Algunos puntos clave para recordar:
- Cada nivel del BFS representa un día de propagación.
- Solo se visitan nodos con valor 1 (naranjas frescas).
- Las naranjas con valor 2 son los puntos de inicio del recorrido.
- Los espacios con valor 0 se ignoran porque no hay planta que contagiar.
Una pregunta interesante que surge es si este problema podría resolverse también con DFS (Depth-First Search), un recorrido en profundidad. DFS explora tan lejos como puede por una rama antes de retroceder, lo que dificulta contar los días correctamente por niveles. Reflexionar sobre las diferencias entre ambos enfoques y su eficiencia temporal es un ejercicio valioso para profundizar en teoría de grafos. ¿Qué opinas tú, se podría usar DFS con la misma eficiencia? Comparte tu razonamiento en los comentarios.
