Si alguna vez te has preguntado qué tipo de problemas aparecen en las entrevistas técnicas de empresas como Google, Microsoft o Facebook, el problema de número de islas es uno de los más recurrentes. Se trata de un ejercicio que combina matrices, recorridos y pensamiento algorítmico, y su comprensión abre la puerta a dominar técnicas fundamentales de grafos.
¿Qué es el problema de número de islas?
El planteamiento parte de una matriz binaria de M por N [0:22]. Esto significa que cada celda solo puede contener dos valores posibles: uno o cero. El valor uno representa tierra y el valor cero representa agua. El objetivo es contar cuántas islas existen dentro de ese mapa.
Una isla se define como un grupo de celdas con valor uno que están conectadas de forma adyacente [0:44]. Dos pedazos de tierra que se tocan horizontal o verticalmente no cuentan como islas separadas, sino como una sola isla más grande. Este concepto de adyacencia es clave para resolver el problema correctamente.
¿Qué sucede con los bordes de la matriz?
Una consideración importante es que los cuatro bordes de la cuadrícula se asumen rodeados de agua [0:56]. Esto quiere decir que si una porción de tierra toca el borde de la matriz, puedes tratarla como si estuviera rodeada de agua en ese lado. No necesitas preocuparte por lo que hay "fuera" del mapa.
¿Cómo luce una entrada de datos típica?
La entrada es una matriz con unos y ceros distribuidos [1:12]. A simple vista, un humano puede identificar rápidamente cuántas islas hay. En el ejemplo presentado, se distinguen tres islas. Sin embargo, el verdadero reto aparece cuando la matriz es enorme, como si representara el mapa de todo el mundo.
¿Cómo se resuelve usando DFS?
El algoritmo propuesto para abordar este problema es DFS (Depth-First Search), un recorrido en profundidad que ya se estudia previamente en el curso [1:30]. La idea general funciona así:
- Recorrer cada celda de la matriz.
- Cuando encuentras un uno (tierra), incrementar el contador de islas.
- Desde esa celda, ejecutar DFS para marcar todas las celdas adyacentes conectadas como visitadas.
- Continuar el recorrido sin volver a contar tierra que ya fue explorada.
De esta forma, cada vez que se encuentra un nuevo pedazo de tierra no visitado, se sabe que pertenece a una isla diferente. El DFS se encarga de "absorber" toda la tierra conectada en una sola pasada.
¿Por qué es tan relevante en entrevistas técnicas?
Este problema evalúa varias habilidades simultáneamente:
- Manejo de matrices bidimensionales y su recorrido eficiente.
- Comprensión de algoritmos de búsqueda en grafos como DFS o BFS.
- Capacidad para transformar un problema visual en una solución algorítmica.
- Pensamiento sobre complejidad temporal y espacial, ya que la solución debe escalar cuando los datos crecen.
Lo interesante es que un problema puede resolverse de múltiples maneras. DFS es una opción, pero también podrías considerar Breadth-First Search (BFS) o incluso estructuras como Union-Find para agrupar las celdas de tierra.
Antes de ver la implementación, el ejercicio más valioso es describir tu propia solución con palabras. ¿Cómo recorrerías la matriz? ¿Cómo marcarías las celdas visitadas? ¿Qué estructura de datos usarías? Comparte tu enfoque y revisa las propuestas de otros para enriquecer tu comprensión del problema.
