Implementación de "Número de Islas" con Recursión en Python

¿Cómo implementar un algoritmo para contar el número de islas usando recursión en Python?

Para quienes buscan adentrarse en el mundo de algoritmos y estructuras de datos, Python ofrece una plataforma versátil para implementar soluciones efectivas. En este caso, vamos a desglosar un método para contar el número de islas en un mapa, usando la técnica de recursión y el lenguaje Python. Este ejercicio te permitirá fortalecer tus habilidades de programación, comprender mejor la recursión y aplicar algoritmos de búsqueda profunda (DFS).

¿Cómo se estructura el enfoque para contar islas?

El primer paso crucial es entender la estructura del problema: un mapa representado por una matriz en la que '1' indica tierra y '0' agua. La meta es identificar grupos conectados de '1' que formen islas. Comenzamos con la implementación de la función inicial que recorre el mapa.

def numero_de_islas(mapa):
    cantidad_de_islas = 0

• Inicialización: La variable cantidad_de_islas se establece en cero antes de revisitar el mapa, ya que al final se desea retornar esta cuenta.
• Iteración sobre el mapa: Recorreremos cada posición (i, j) para determinar si el elemento es tierra o agua.

¿Qué implica detectar la presencia de una isla?

Para detectar una isla, verificamos si la posición actual en la matriz contiene un '1', lo que indica tierra. Si es así, se descubre una nueva isla, pero debemos procurar no contar las mismas secciones de tierra más de una vez.

for i in range(len(mapa)):
    for j in range(len(mapa[0])):
        if mapa[i][j] == 1:
            cantidad_de_islas += 1  # Nueva isla encontrada
            dfs(mapa, i, j)  # Llamado a DFS para explorar la isla entera

¿Cómo aplicar búsqueda en profundidad (DFS) de manera eficaz?

DFS nos permite explorar cada parte de la isla (cada '1' conectado) marcando el recorrido para evitar contar la misma isla repetidas veces. Utilizaremos una función recursiva adicional para esta tarea.

def dfs(mapa, i, j):
    # Retorna si estamos fuera de los límites o si no es tierra
    if i < 0 or j < 0 or i >= len(mapa) or j >= len(mapa[0]) or mapa[i][j] != 1:
        return
    
    mapa[i][j] = 2  # Marca como visitada la posición actual

    # Explora las direcciones vecinas
    dfs(mapa, i - 1, j)  # Arriba
    dfs(mapa, i + 1, j)  # Abajo
    dfs(mapa, i, j - 1)  # Izquierda
    dfs(mapa, i, j + 1)  # Derecha

• Marcado de visitados: Se asigna un valor inexistente como '2' para indicar que el terreno ya se ha procesado, emulando así las 'migas de pan' del cuento de Hansel y Gretel para evitar revisitas.
• Límites de array: Asegurarse de trabajar dentro de los límites de la matriz para prevenir errores de acceso no definido.

¿Cuáles son las implicaciones de complejidad del algoritmo?

Este algoritmo recorre el mapa una sola vez, garantizando una eficiencia de O(n*m), donde n es el número de filas y m el número de columnas en el mapa.

La recursión, si bien elegante, puede no ser siempre la solución más eficiente en recursos, especialmente en escenarios donde el mapa es extenso y el stack de llamadas es profundo. Invitaría a los estudiantes a implementar la solución iterativa también, ayudándoles a cimentar el conocimiento desde diferentes perspectivas.

En conclusión, este ejercicio práctico no solo refuerza conceptos de programación, sino que también invita a la improvisación y experimentación para optimizar y encontrar soluciones novedosas a un problema clásico en el campo de la informática. ¡Anímate a ponerlo en práctica y sigue avanzando en el fascinante mundo de la tecnología!