Resolver el problema de número de islas con DFS recursivo en Python te enseña a recorrer matrices, marcar posiciones visitadas y entender la complejidad temporal de un algoritmo de búsqueda en profundidad. Es una técnica clave para entrevistas técnicas y para cualquier desarrollador que quiera dominar recursión sobre estructuras bidimensionales.

¿Cómo se estructura la función principal número de islas?

La función recibe un mapa (matriz de ceros y unos) y devuelve cuántas islas existen. El primer paso es declarar una variable cantidad_de_islas inicializada en cero, que será el valor a retornar al final del recorrido [0:30].

Después viene la iteración doble sobre filas y columnas usando los índices i y j. Como todas las filas tienen la misma longitud, puedes usar len(mapa[0]) para definir el rango de columnas sin afectar el resultado.

¿Qué hace la función número de islas? Recorre cada celda del mapa. Cuando encuentra tierra (valor 1), incrementa el contador y lanza un DFS para marcar toda la isla conectada antes de seguir buscando.

¿Cuándo debo aumentar el contador de islas?

Solo cuando llegas a una celda con tierra que aún no has visitado. Si la celda actual es agua, sigues navegando. Si es tierra, primero recorres toda la isla con DFS y solo entonces sumas uno al contador [2:00].

Esto evita contar como islas separadas pedazos de tierra que en realidad están conectados. La regla es simple: una isla se cuenta una sola vez, sin importar cuántas casillas la compongan.

¿Cómo funciona el DFS recursivo para recorrer una isla?

La función auxiliar dfs(i, j) se encarga de profundizar en la isla hasta agotar todas las celdas conectadas. Recibe las coordenadas actuales y se llama a sí misma cuatro veces, una por cada dirección: arriba, abajo, izquierda y derecha [3:30].

La idea central es la analogía de Hansel y Gretel: dejar migajas para no volver a pisar el mismo terreno. En código, esto se traduce en cambiar el valor de la celda visitada de 1 a 2, marcando que ya estuviste ahí.

python def numero_de_islas(mapa): cantidad_de_islas = 0

def dfs(i, j):
    if i < 0 or i >= len(mapa):
        return
    if j < 0 or j >= len(mapa[0]):
        return
    if mapa[i][j] == 1:
        mapa[i][j] = 2
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

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

¿Por qué marcar las celdas visitadas con un 2?

Porque necesitas un valor que no se confunda con tierra (1) ni con agua (0). Al pintar la celda con 2, garantizas que la próxima vez que el DFS pase por ahí no entre al bloque condicional y no caigas en un ciclo infinito [4:45].

Esta técnica de modificar la matriz original ahorra memoria porque evitas crear una matriz auxiliar de visitados. Es un truco común en problemas de grids cuando puedes mutar la entrada.

¿Cómo manejar los bordes del mapa en la recursión?

Cuando estás en una esquina y llamas a dfs(i - 1, j) con i = 0, terminas accediendo a un índice fuera del arreglo. Para evitar este error, agregas validaciones al inicio de la función [5:30].

Las condiciones que protegen los bordes son:

• Verificar que i esté entre 0 y len(mapa).
• Verificar que j esté entre 0 y len(mapa[0]).
• Solo procesar la celda si su valor es exactamente 1.

¿Qué pasa si no valido los índices en DFS? El programa lanza un IndexError al intentar acceder a una posición que no existe en la matriz. Las validaciones evitan ese fallo y permiten que la recursión termine de forma segura.

¿Cuál es la complejidad temporal del algoritmo?

La complejidad temporal es O(N²), donde N es la longitud de uno de los lados del mapa. Aunque parezca que recorres el mapa varias veces por las llamadas recursivas del DFS, en realidad cada celda se visita una sola vez gracias al marcado con 2 [7:30].

La función externa itera sobre todas las celdas y la función DFS solo entra en celdas con valor 1, que después convierte en 2. Por eso el trabajo total es proporcional al número de casillas del mapa.

¿Y la complejidad espacial?

Ese es el reto. Piensa en cuántas llamadas recursivas pueden estar apiladas al mismo tiempo en el peor caso, cuando toda la matriz es tierra y el DFS profundiza sin parar. Deja tu respuesta en los comentarios.

También te invito a reescribir la solución de forma iterativa usando una pila o cola explícita. Comparar ambas versiones te ayuda a entender mejor cómo la recursión usa el stack del sistema y cuándo conviene cambiar a un enfoque iterativo.

Haz pruebas de escritorio línea por línea con un mapa pequeño. Es la mejor forma de cogerle el tiro a la recursión y detectar errores antes de que aparezcan en producción.