El problema número de islas aparece con frecuencia en entrevistas técnicas de empresas como Google, Microsoft o Facebook, y entender cómo abordarlo te prepara para resolver retos de matrices y grafos en cualquier proceso de selección. Aquí desglosamos el enunciado, los conceptos que necesitas dominar y la pista que te llevará a tu propia solución.

¿En qué consiste el problema número de islas?

La idea es trabajar con una matriz binaria de tamaño M por N, donde cada casilla solo puede contener el valor uno o cero. Cada número representa un tipo de terreno distinto y tu tarea es contar cuántas islas existen en ese mapa.

• El valor 1 representa tierra.
• El valor 0 representa agua.
• El resultado esperado es un entero: el número total de islas.

¿Qué es una matriz binaria? Es una estructura bidimensional donde cada celda solo admite dos valores posibles, típicamente 0 y 1. Sirve para modelar mapas, imágenes en blanco y negro o cualquier estado dual.

¿Cómo se define una isla en este contexto?

Una isla es un grupo de tierra rodeada de agua que se forma conectando casillas adyacentes con valor uno. Si dos pedazos de tierra están pegados horizontal o verticalmente, no cuentan como dos islas separadas, sino como una sola isla más grande [01:00].

Además, puedes asumir que los cuatro bordes de la cuadrícula están rodeados de agua. Esto significa que una isla pegada a una esquina sigue siendo una isla válida, aunque no veas agua en dos de sus lados.

¿Cómo se ve una entrada de datos típica?

Imagina una matriz llena de unos y ceros. A simple vista, como humano, puedes detectar tres islas en un ejemplo pequeño solo mirando los grupos conectados de unos [01:30]. El reto aparece cuando la matriz crece.

¿Qué pasa si el mapa representa una región enorme, con miles o millones de celdas? Ahí es donde un algoritmo se vuelve indispensable, porque tu ojo ya no alcanza y necesitas una estrategia sistemática para recorrer cada celda y agrupar las tierras conectadas.

¿Por qué este problema es popular en entrevistas? Porque combina recorrido de matrices, conectividad entre nodos y pensamiento en grafos. Permite evaluar si sabes aplicar búsquedas como DFS o BFS sobre estructuras no triviales.

¿Qué algoritmo puedes usar para resolverlo?

La pista directa que te da la clase es usar DFS, es decir, Depth First Search o búsqueda en profundidad, un algoritmo que ya cubrimos antes en el curso [01:50]. La intuición es simple: recorres la matriz celda por celda, y cuando encuentras un uno, exploras en profundidad todas las tierras conectadas a esa casilla, marcándolas como visitadas. Cada vez que inicias una nueva exploración desde un uno no visitado, sumas una isla al contador.

• Recorres la matriz con dos bucles anidados.
• Cuando encuentras una celda con valor uno sin visitar, incrementas el contador.
• Lanzas una búsqueda en profundidad para marcar toda la isla conectada.
• Continúas hasta cubrir todas las celdas.

No es la única ruta posible. También podrías pensar en Breadth First Search o en estructuras como Union Find, que agrupan elementos conectados de forma eficiente.

¿Cuál es tu reto antes de la siguiente clase?

Antes de ver la solución implementada, tu trabajo es diseñar tu propio enfoque. No necesitas escribir código todavía, solo describir el proceso paso a paso: cómo recorrerías la matriz, cómo decidirías que una celda pertenece a una isla ya contada y cómo evitarías visitar la misma tierra dos veces.

Deja tu propuesta en los comentarios, lee las de tus compañeros y comenta las que te parezcan interesantes. Nos vemos en la siguiente clase.