Resolver el problema de contar islas en una matriz es una de las preguntas más frecuentes en entrevistas técnicas de empresas como Google, Microsoft, Amazon y Facebook. Comprender cómo abordarlo no solo prepara para esas entrevistas, sino que también refuerza habilidades fundamentales en recorrido de grafos y recursión.
¿Qué es el problema de número de islas y por qué importa?
El planteamiento es directo: se tiene una matriz de números compuesta únicamente por unos y ceros [0:32]. Los unos representan tierra y los ceros representan agua. El objetivo es contar cuántas islas existen en esa matriz. Una isla se define como un cuerpo de tierra completamente rodeado de agua por todos sus lados.
Lo interesante es que, aunque la estructura de datos es una simple matriz, el problema se puede abordar como un problema de grafos [1:06]. No se necesita una estructura explícita de nodos y relaciones. Cada celda de la matriz tiene hasta cuatro vecinos: arriba, abajo, izquierda y derecha. Esa relación implícita entre celdas adyacentes convierte la matriz en un grafo donde cada celda es un nodo y cada vecino es una conexión.
¿Cómo se recorre la matriz para encontrar islas?
La estrategia se basa en DFS (Depth First Search), es decir, búsqueda en profundidad [2:23]. La idea es recorrer la matriz celda por celda y, cuando se encuentra tierra (un uno), adentrarse lo más posible explorando todos los vecinos de tierra antes de retroceder.
¿Qué pasa cuando encuentro tierra?
Al llegar a una celda con valor uno, se activa una función recursiva de DFS [4:25]. Esta función revisa las cuatro direcciones adyacentes:
- Si el vecino también es tierra, se sigue explorando en esa dirección.
- Si el vecino es agua o está fuera de los límites, se detiene esa rama.
El punto clave es que no basta con encontrar agua en un solo vecino para determinar que la isla terminó [3:47]. Todos los bordes de la porción de tierra deben estar rodeados de agua. Mientras exista al menos un vecino con tierra, la exploración continúa porque se trata de la misma isla.
¿Cómo se distingue entre una isla y otra?
Cada vez que la iteración principal encuentra un uno que no ha sido visitado, se ejecuta DFS completo sobre toda esa isla. Al terminar, un contador se incrementa en uno [4:42]. Cuando DFS finaliza para una isla, significa que toda la tierra contigua ya fue marcada como visitada. Al continuar iterando por la matriz, cualquier nuevo uno encontrado pertenece necesariamente a una isla diferente.
El proceso completo es:
- Iterar por cada celda de la matriz.
- Si la celda es agua (cero), avanzar.
- Si la celda es tierra (uno), ejecutar DFS para marcar toda la isla.
- Incrementar el contador de islas.
- Continuar hasta recorrer toda la matriz.
¿Cuál es la complejidad del algoritmo?
La complejidad temporal es O(n²), donde n es la longitud del lado de la matriz [5:03]. Se debe visitar cada celda al menos una vez para determinar si es tierra o agua.
La complejidad espacial también es O(n²) [5:16]. Esto se debe a la naturaleza de la recursión: cada llamada recursiva de DFS se apila en la call stack (pila de llamadas). En el peor caso, si toda la matriz fuera tierra, la profundidad de recursión alcanzaría el número total de celdas. Esa memoria adicional es necesaria porque al salir de cada nivel de recursión, el programa necesita recordar el estado previo para continuar la exploración.
Un detalle valioso para entrevistas: si el problema no especifica las direcciones válidas, conviene preguntar si las diagonales también cuentan como celdas adyacentes [3:21]. Esa pregunta demuestra capacidad de análisis y atención al detalle, cualidades que los entrevistadores valoran.
Existen otras formas de resolver este problema, como utilizar BFS (Breadth First Search) en lugar de DFS, o aplicar la técnica de Union-Find. ¿Conoces alguna otra aproximación o dividirías el problema en subproblemas diferentes? Comparte tu enfoque en los comentarios.
