Resolver el problema de número de islas es uno de los ejercicios más representativos para dominar búsqueda en profundidad y recursión. Aquí se implementa paso a paso en Python una solución que recorre un mapa bidimensional, identifica cada isla y la marca para no contarla dos veces, todo con una complejidad temporal de O(n²).
¿Cómo se estructura la solución para contar islas?
La función principal se llama numero_de_islas y recibe un mapa representado como una matriz de ceros y unos. El primer paso es declarar una variable cantidad_de_islas inicializada en cero, que será el valor de retorno al finalizar el recorrido [0:38].
Después se itera sobre cada posición del mapa usando dos bucles anidados: uno para las filas (i) y otro para las columnas (j). En cada coordenada (i, j) se verifica si el valor es 1, es decir, si se trata de tierra [1:07]. Cuando se encuentra tierra, no se incrementa el contador de inmediato. Primero se ejecuta una función auxiliar llamada DFS (Depth-First Search) que se encarga de recorrer toda la isla conectada antes de sumar uno al contador [1:36].
Esta decisión es fundamental: si se sumara al contador cada vez que se encuentra un 1, cada celda de tierra contaría como una isla independiente. Lo correcto es explorar toda la extensión de la isla y solo entonces registrarla como una unidad.
¿Cómo funciona la búsqueda en profundidad con recursión?
La función DFS(i, j) es el corazón de la solución. Recibe las coordenadas actuales y realiza tres acciones clave [2:15]:
- Valida los límites: antes de acceder a cualquier posición, comprueba que
i esté dentro del rango de filas y j dentro del rango de columnas. Sin esta verificación, al estar en un borde o esquina del mapa, se intentaría acceder a una posición fuera de la memoria y se produciría un error [3:20].
- Verifica que la celda sea tierra: solo actúa si
mapa[i][j] == 1.
- Marca la celda como visitada: asigna el valor
2 a esa posición. Esta técnica se describe como "dejar migajitas", similar al cuento de Hansel y Gretel [2:30]. Donde antes había un 1, ahora hay un 2, lo que impide volver a procesar esa celda.
Una vez marcada, la función se llama a sí misma cuatro veces para explorar las celdas adyacentes en las cuatro direcciones cardinales [3:05]:
python
def dfs(i, j):
if 0 <= i < len(mapa) and 0 <= j < len(mapa[0]) and mapa[i][j] == 1:
mapa[i][j] = 2
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
Cada llamada recursiva profundiza en una dirección hasta que ya no hay más tierra conectada. Así se garantiza que toda la isla quede marcada antes de regresar al bucle principal.
¿Por qué la complejidad temporal es O(n²)?
Aunque se invoca una función recursiva dentro de un doble bucle, el mapa se recorre una sola vez en la práctica [4:30]. La función DFS modifica los valores de 1 a 2, por lo que las celdas ya visitadas no vuelven a procesarse. Si n representa la longitud de un lado del mapa cuadrado, se visitan n × n celdas, resultando en una complejidad temporal O(n²).
La estructura completa de la función principal queda así:
python
def numero_de_islas(mapa):
cantidad_de_islas = 0
for i in range(len(mapa)):
for j in range(len(mapa[0])):
if mapa[i][j] == 1:
dfs(i, j)
cantidad_de_islas += 1
return cantidad_de_islas
¿Qué buenas prácticas refuerza este ejercicio?
- Separar la lógica de exploración en una función auxiliar (
dfs) mantiene el código limpio.
- Marcar celdas visitadas con un valor distinto evita ciclos infinitos y conteos duplicados.
- Validar límites del arreglo antes de acceder previene errores de índice.
¿Cómo practicar recursión de forma efectiva?
Realizar pruebas de escritorio línea a línea con una entrada concreta es esencial para entender cómo cada llamada recursiva genera subproblemas anidados [5:12]. Sin esa claridad, es fácil cometer errores al programar soluciones recursivas.
Un reto adicional que vale la pena intentar: implementar la misma solución de forma iterativa, utilizando una pila explícita en lugar de la pila de llamadas del sistema. ¿Te animas a compartir tu versión iterativa en los comentarios?
