El problema de número de islas es uno de los favoritos en entrevistas técnicas de Google, Microsoft, Amazon y Facebook, y entender cómo resolverlo con DFS te abre la puerta a pensar cualquier matriz como un grafo. Aquí desglosamos la lógica paso a paso para que sepas atacarlo cuando te lo pregunten.

¿Qué pide el problema de número de islas?

Imagina una matriz llena de unos y ceros. Los unos representan tierra, los ceros representan agua, y tu misión es contar cuántas islas existen. Una isla es un grupo de tierra rodeado completamente por agua.

Lo interesante aparece cuando dejas de ver la matriz como números y empiezas a verla como un mapa. Si tienes un tablero pequeño, puedes contar a simple vista. Pero si te dan un mapa del mundo entero, necesitas un algoritmo que recorra cada celda con criterio.

¿Qué cuenta como una isla en este problema? Un grupo de celdas con valor 1 que están conectadas entre sí por arriba, abajo, izquierda o derecha. Si están separadas por agua, son islas distintas.

¿Por qué una matriz se puede tratar como un grafo?

Aquí está el giro mental clave. Un grafo tradicional se ve como nodos y relaciones explícitas. Pero una matriz también es un grafo: cada celda es un nodo y sus vecinos (arriba, abajo, izquierda, derecha) son sus relaciones [01:20].

Esto significa que técnicas como recorrido en profundidad o en anchura no solo sirven para estructuras de datos complejas. Sirven cada vez que tengas elementos con vecinos definidos, incluso si tu input es un simple arreglo bidimensional.

¿Cómo recorremos el mapa con DFS?

La estrategia es usar Depth First Search: te metes en una dirección hasta que ya no puedas avanzar, y entonces retrocedes a explorar las otras direcciones [03:10]. Aplicado al mapa, significa que cuando encuentras tierra, te adentras en esa isla hasta agotar todas las celdas conectadas antes de seguir buscando.

Gráficamente, recorres la matriz celda por celda haciendo paradas y comparaciones según el estado de cada posición.

¿Cómo se manejan los estados de tierra y agua?

Tienes dos estados posibles: agua o tierra. Y según en cuál estés, el algoritmo hace cosas distintas.

• Si estás en agua (cero), simplemente avanzas a la siguiente celda.
• Si estás en tierra (uno), revisas si las celdas adyacentes también son tierra para saber si pertenecen a la misma isla.
• Si todos los bordes alrededor de tu zona de tierra son agua, terminaste de mapear esa isla.

La condición de cierre no es encontrar un solo cuadrito de agua. Es que todo el contorno de tu pedazo de tierra sea agua. Solo ahí cuentas una isla completa.

¿Cuándo dejo de explorar una isla? Cuando todas las celdas adyacentes a la zona de tierra que estás recorriendo son agua o están fuera del mapa. Ese es el borde real de la isla.

¿Qué pasa con las diagonales?

Un detalle que vale la pena preguntar en la entrevista: ¿las diagonales cuentan como adyacentes? El planteo estándar considera solo arriba, abajo, izquierda y derecha, pero confirmar este supuesto demuestra criterio [05:00].

¿Cómo se estructura el algoritmo final?

La solución combina dos piezas: una función grande que itera la matriz completa, y una función auxiliar que hace DFS cada vez que encuentra tierra.

1. Recorres cada celda de la matriz con dos bucles anidados.
2. Si la celda vale 0, sigues iterando.
3. Si la celda vale 1, llamas a la función DFS que marca toda la isla conectada.
4. Cada vez que termina una llamada a DFS, sumas 1 al contador de islas.
5. Cuando recorriste todo el tablero, el contador tiene la respuesta.

Esa función DFS se llama recursivamente sobre las cuatro direcciones posibles desde cada celda de tierra, marcando lo visitado para no contar la misma isla dos veces.

¿Cuál es la complejidad de la solución?

La complejidad temporal es N al cuadrado, donde N es el ancho o largo de la matriz si asumimos un tablero cuadrado [07:30]. Esto se debe a que tienes que visitar cada celda al menos una vez.

La complejidad espacial también es N al cuadrado. La razón está en la recursión: cada llamada a DFS dentro de DFS agrega un frame a la pila de memoria. En el peor caso, si toda la matriz es una sola isla gigante, la pila guarda información de cada celda visitada.

¿Por qué la recursión consume memoria? Cada llamada recursiva guarda su contexto en la pila para poder regresar al punto anterior cuando termina. Si llamas DFS dentro de DFS muchas veces, esa pila crece proporcionalmente.

¿Hay otras formas de resolver el problema?

DFS no es la única vía. También puedes usar BFS recorriendo por niveles con una cola, o estructuras como Union Find para agrupar celdas conectadas. Cada enfoque tiene trade-offs distintos en memoria y claridad.

Cuéntame en los comentarios cómo lo abordarías tú, qué subproblemas identificas y si conoces alguna variante que optimice memoria o tiempo.