Introducción

1

Grafos y Árboles: Estructuras de Datos Avanzadas

2

Estructuras de Datos: Introducción a Árboles y Sus Propiedades

3

Recursión: Concepto y Aplicaciones Prácticas con Ejemplos

4

Aplicaciones Prácticas de Grafos en Tecnología e Industria

5

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

6

Búsqueda en Profundidad (DFS) en Árboles y Grafos

7

Implementación de DFS recursivo para búsqueda en árboles

8

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

9

Recorridos y Profundidad en Árboles Binarios y Enearios

10

Suma de Caminos en Árboles Binarios

11

Suma de Números de Raíz a Hoja en Árboles

12

Playground: Sum Root to Leaf Numbers

13

Implementación de Algoritmo DFS en Árboles Binarios con Golang

14

Resolución del Problema de Número de Islas con DFS

15

Conteo de Islas en Matrices con DFS

16

Playground: Number of Islands

17

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

18

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

19

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

20

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

21

Implementación de BFS en Árboles usando Python

22

Movimiento mínimo de caballo en ajedrez infinito

23

Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez

24

Playground: Minimum Knights Moves

25

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

26

Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total

27

Resolución de Rotting Oranges usando BFS

28

Playground: Rotting Oranges

29

Propagación de Plagas en Matrices usando BFS en Java

30

Construcción de Puentes Cortos entre Islas en Matrices Binarias

31

Resolución del Problema Shortest Bridge con DFS y BFS

32

Playground: Shortest Bridge Between Islands

33

Búsqueda del camino más corto entre islas usando BFS en Python

34

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

35

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

36

Algoritmo Backtracking: Solución de Problemas Complejos

37

Combinaciones de Letras en Números Telefónicos

38

Combinaciones de Letras a partir de un Número de Teléfono

39

Generación de combinaciones de letras con teclados numéricos en C++

40

Playground: Letter Combinations of a Phone Number

41

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

42

Generación de IPs válidas con backtracking en C++

43

Playground: Restore IP Addresses

44

Búsqueda de Palabras en Matrices: Solución y Complejidad

45

Búsqueda de Palabras en Matrices usando Backtracking y DFS

46

Playgrund: Word Search

47

Implementación de búsqueda de palabras en matrices con DFS en JavaScript

48

Resolución del problema de las n reinas en ajedrez

49

Ejercicios de Backtracking: Combinaciones y Permutaciones

50

Combinaciones y Permutaciones con Backtracking

Próximos pasos

51

Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra

52

Algoritmos y Estructuras de Datos en la Ingeniería

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

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

17/52
Recursos

¿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!

Aportes 8

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

**Tengo una duda:Tengo una duda:** ¿Cómo es posible que la función `dfs()` acceda y modifique los valores de la matriz `mapa` si no recibe este parámetro en su definición y tampoco se ha declarado como una variable global? ¿Cómo es posible que la función `dfs()` acceda y modifique los valores de la matriz `mapa` si no recibe este parámetro en su definición y tampoco se ha declarado como una variable global? Esta es mi solucion ```js def dfs(i , j , mapa): if 0 <= i < len(mapa) and 0 <= j < len(mapa[0]) and mapa[i][j] == "1": mapa[i][j] = "2" dfs(i + 1 , j, mapa) dfs(i - 1 , j, mapa) dfs(i , j + 1, mapa) dfs(i , j - 1, mapa) return mapa def numeroDeIslas(mapa): islands = 0 for i in range(len(mapa)): for j in range(len(mapa[0])): if mapa[i][j] == "1": islands += 1 mapa = dfs(i , j , mapa) return islands ```

En Java

class Solution {
    static int islandNumbers;
    public int numIslands(char[][] grid) {
        islandNumbers = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length ; j++){
                if(grid[i][j] == '1'){
                    dfs(i,j, grid);
                    islandNumbers++;
                }
            }
        }
        return islandNumbers;
    }

    public void dfs(int i, int j, char[][] grid){
        if(i>=0 && i<grid.length && j>=0 && j<grid[0].length && grid[i][j] == '1'){
            grid[i][j] = '2';
            dfs(i, j+1, grid); 
            dfs(i, j-1, grid);
            dfs(i+1, j, grid);
            dfs(i-1, j, grid);

        }
    }
}

Esta es mi solución en Kotlin:

fun main() {
    val map = listOf(
        mutableListOf(1, 1, 0, 0, 0, 0, 1, 0),
        mutableListOf(1, 0, 0, 1, 1, 0, 0, 0),
        mutableListOf(0, 0, 0, 1, 1, 0, 0, 1),
        mutableListOf(0, 0, 0, 0, 0, 1, 1, 1),
    )

    val count = countIslands(map);

    println("The number of Island in the map is: $count")
}

fun countIslands(map: List<MutableList<Int>>): Int {
    var count = 0
    for (i in map.indices) {
        for (j in map[i].indices) {
            if (map[i][j] == 1) {
                inspectIsland(map, i, j)
                count++
            }
        }
    }
    return count
}
En mi opinión la complejidad espacial seria O(n\*m): El mapa se crea al inicio y ambas funciones hacen uso de la misma matriz, como si esta fuera una variable global, breve; esto sería O(1), por aquí no hay lio. Sin embargo las variables i, j que recibe dfs() se van creando nuevas en la medida que dfs() se ejecuta recursivamente añadiendo capas nuevas a la pila. En el peor de los casos donde la matriz esta llena de 1s la función dfs() debe propagarse por todo el tablero creando variables i, j para cada elemento de la matriz, por tanto la complejidad espacial seria el tamaño de la matriz O(n\*m)
esta es mi solucion en java ```java public class NumberOfIslands { public static void main(String[] args) { int[][] map = buildMap(); System.out.printf("islands found: [%d]\n", findNumberOfIslands(map)); } private static int findNumberOfIslands(int[][] map) { if(map == null || map.length == 0){ return 0; } printMap(map); int numberOfIslands = 0; for(int i = 0; i < map.length; i++){ for(int j = 0; j < map[i].length; j++){ if(map[i][j] == 1){ numberOfIslands += dfs(map, i, j); printMap(map); } } } return numberOfIslands; } private static int dfs(int[][] map, int i, int j) { if(i < 0 || j < 0 || i >= map.length || j >= map[i].length || map[i][j] == 0){ return 0; } // mark point as visited map[i][j] = 0; // move right dfs(map, i + 1, j); // move left dfs(map, i+1, j); // move down dfs(map, i, j+1); // move up dfs(map, i, j-1); return 1; } private static void printMap(int[][] map){ for (int[] ints : map) { for (int j = 0; j < ints.length; j++) { System.out.print(ints[j]); if (j == ints.length - 1) { System.out.print("\n"); } else { System.out.print(", "); } } } System.out.println("----------------"); } private static int[][] buildMap() { return new int[][] { {0,0,0,0,1,1,0,0}, {0,1,1,1,0,0,0,1}, {0,1,1,0,0,1,1,1}, {0,0,0,0,0,1,1,0}, }; } } ```
Que bueno! No se me ocurrió esto, pensé que en el ciclo iba a entrar por la tierra adyacente, pero no pensé que en la función dfs, cambiamos el valor en mapa\[i]\[j] a 2. Entonces no va a entrar al if 🤯 ahí está la clave
La solución pasada a C# `List<List<int>> inputData = new()` `{` ` new List<int>() { 1, 1, 1, 0, 0 },` ` new List<int>() { 1, 1, 0, 0, 0 },` ` new List<int>() { 0, 0, 0, 1, 1 },` ` new List<int>() { 1, 1, 0, 0, 0 },` ` new List<int>() { 1, 1, 0, 1, 1 }` `};` `void dfsInslands(int i, int j)` `{` ` if (0 <= i && i < inputData.Count && 0 <= j && j < inputData.Count && inputData[i][j] == 1)` ` {` ` inputData[i][j] = 2;` ` dfsInslands(i + 1, j);` ` dfsInslands(i - 1, j);` ` dfsInslands(i, j - 1);` ` dfsInslands(i, j + 1);` ` }` `}` `int CountIslands(List<List<int>> islands)` `{` ` int count = 0;` ` for (int i = 0; i < islands.Count; i++)` ` for (int j = 0; j < islands.Count; j++)` ` if (islands[i][j] == 1)` ` {` ` dfsInslands(i, j);` ` count++;` ` }` ` return count;` `}` `Console.WriteLine("TOTAL OF ISLANDS {0}",CountIslands(inputData));`

Jeje si leí el cuento de Hansel y Gretel.