Curso de Algoritmos Avanzados: Grafos y Árboles
Curso de Algoritmos Avanzados: Grafos y Árboles

Introducción

1

Estructuras de Datos: Grafos y Árboles en Profundidad

2

Estructuras de Árbol: Nodos, Raíces y Jerarquías

3

Recursión y secuencia de Fibonacci en programación

4

Aplicaciones Prácticas de Grafos en Tecnología

5

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

6

Recorrido en Profundidad (DFS) en Árboles y Grafos

7

Algoritmo DFS en JavaScript: Búsqueda en Árboles

8

Búsqueda en Profundidad (DFS) en Grafos: Iterativa y Recursiva

9

Recorridos en Árboles: Inorder, Preorder y Postorder

10

Suma de Números en Caminos Raíz-Hoja en Árboles Binarios

11

Suma de Caminos en Árbol con DFS en Python

12

Playground: Sum Root to Leaf Numbers

13

Implementación de Árboles Binarios en Golang

14

Algoritmo DFS para Contar Islas en Matrices Binarias

15

Conteo de Islas en Matrices con DFS

16

Playground: Number of Islands

17

Programación Recursiva: Resolver Problemas con DFS en Python

18

Rellenar Sección de Imagen con Algoritmo DFS

19

Búsqueda en Profundidad para Procesamiento de Imágenes

BFS

20

Algoritmo BFS: Exploración en Anchura de Grafos y Árboles

21

Implementación de BFS en Árboles con Python

22

Algoritmo BFS para mover el caballo de ajedrez

23

Saltos mínimos con caballo en ajedrez infinito: Resuelve BFS.

24

Playground: Minimum Knights Moves

25

Suma de matrices en Python: Paso a Paso

26

Propagación de Plagas en Matrices: Cálculo de Días Totales

27

Propagación de plagas con BFS en matrices cuadradas

28

Playground: Rotting Oranges

29

Matrices y Algoritmos: Implementación en Java

30

Puente más Corto entre Islas en Matrices Binarias

31

Construcción de Puentes Cortos entre Islas en Matrices Numéricas

32

Playground: Shortest Bridge Between Islands

33

Resuelve problemas con el algoritmo Breadth-First Search en Python

34

Búsqueda Breadth-First (BFS) en Grafos: Conceptos y Ejercicios

35

Búsqueda en Anchura para Problemas de Grafos

Backtrack

36

Solución de Problemas con Algoritmo Backtracking en Laberintos

37

Combinaciones de Letras en Números Telefónicos

38

Combinaciones de Letras en Números Telefónicos con Backtracking

39

C++: Generación de combinaciones en un teclado numérico

40

Playground: Letter Combinations of a Phone Number

41

Formación de direcciones IP válidas a partir de cadenas numéricas

42

Algoritmo para Crear Direcciones IP Válidas en C++

43

Playground: Restore IP Addresses

44

Resolución del Problema Word Search en Tableros MxN

45

Búsqueda de palabras en matrices usando backtracking y DFS

46

Playgrund: Word Search

47

Búsqueda de Palabras en Matrices con JavaScript

48

Algoritmos para resolver N-Reinas en Python

49

Programación backtracking para resolver Sudoku

50

Combinaciones Únicas de Sumas de Enteros

Próximos pasos

51

Árboles AVL: Balanceo Automático en Estructuras de Datos

52

Algoritmos de Búsqueda Eficientes y Su Aplicación Práctica

No tienes acceso a esta clase

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

Si ya tienes una cuenta,

Curso de Algoritmos Avanzados: Grafos y Árboles

Curso de Algoritmos Avanzados: Grafos y Árboles

Camila Londoño

Camila Londoño

Construcción de Puentes Cortos entre Islas en Matrices Numéricas

31/52
Recursos

¿Cómo resolver de manera eficiente el problema de Shortest Bridge?

El problema de Shortest Bridge nos invita a optimizar la construcción de un puente entre dos islas en un mapa representado por ceros y unos. Los ceros representan agua y los unos, tierra. Aunque el objetivo parece simple, la solución implica una combinación ingeniosa de los algoritmos DFS y BFS para determinar el camino más corto posible. A lo largo de este proceso, utilizamos técnicas fundamentales que ya hemos trabajado en ejercicios anteriores. ¡Así que recuerda repasar la búsqueda en profundidad antes de continuar!

¿Cómo identificar la primera isla?

Para detectar la primera isla, empleamos DFS (Depth-First Search). Este algoritmo permite profundizar desde el primer cuadro donde encontramos un "1", lo que identifica el inicio de la isla. Este es un punto de referencia crítico para nuestro problema, ya que desde aquí comenzamos a marcar los bordes de esta isla. Estos límites son esenciales, pues luego servirán como punto de partida para explorar posibles rutas al construir el puente hacia la segunda isla.

  • Utilizamos DFS para identificar y registrar los bordes de la primera isla.
  • Desde el primer "1", el DFS se expande hasta que identifica todos los límites de la isla.
  • Los bordes se almacenan en una estructura tipo stack (pila) propia de DFS.

¿Cómo encontrar el punto más cercano de las dos islas?

Una vez identificados los bordes de la primera isla, es crucial decidir dónde están las dos islas más cerca. La construcción del puente será óptima en el punto donde la distancia entre ambas islas sea mínima.

Para abordar este problema, utilizamos BFS (Breadth-First Search). Avanzamos nivel por nivel desde los bordes de la primera isla hasta encontrar suelo, es decir, cuando nos topamos con un "1" de la segunda isla:

  • Iniciar BFS desde las coordenadas de los bordes (en una estructura de cola).
  • Avanzar por todos los casillas adyacentes: arriba, abajo, izquierda y derecha.
  • Utilizar un hash set para guardar y verificar las coordenadas ya visitadas, evitando redundancias.
  • Detener el proceso tan pronto como alcancemos tierra nuevamente, es decir, la segunda isla.

¿Cómo calcular la cantidad de materiales de construcción del puente?

El número de niveles de BFS que recorremos en el agua nos da la cantidad de material necesario. Sin embargo, tomemos en cuenta que cuando alcanzamos tierra (un "1"), no necesitamos incluir ese nivel en el conteo. El conteo de niveles avanzados menos uno nos proporciona la distancia correcta:

  • Llevar un conteo de los niveles de BFS.
  • Decrementar el conteo en uno al final para obtener la distancia real del puente necesario.

Esta mezcla de DFS y BFS nos brinda una solución eficiente y optimizada para el problema.

¿Qué otras consideraciones se deben tener en cuenta?

Podríamos preguntarnos si es posible invertir las estrategias, utilizando primero BFS y luego DFS. Te animo a reflexionar sobre esto y compartir tus ideas en los comentarios. Estas discusiones enriquecen nuestra comprensión y nos permiten aprender alternativas valiosas para un problema en particular. También te propongo un reto: intenta determinar la complejidad temporal y espacial de esta solución.

Recuerda, el aprendizaje es un proceso continuo, y cada enfoque nos brinda una oportunidad única para desarrollar nuestra habilidad para resolver problemas. ¡Así que sigue explorando, comentando, y nos vemos en la próxima clase para explorar más sobre la implementación de este algoritmo!

Aportes 1

Preguntas 0

Ordenar por:

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

Yojan Antonio Pardo Zabala

Yojan Antonio Pardo Zabala

hace un año
esta es mi solución en java, primero obtengo las coordenadas de la primera isla con DFS y luego desde cada punto de la primera isla hago BFS para encontrar la distancia entre las islas ```java package dev.yojanpardo.grafosarboles.shortestbridge; import dev.yojanpardo.grafosarboles.recursion.Point; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set; public class ShortestBridgeBetweenIslands { private static final Point[] DIRECTIONS = new Point[] { new Point(1,0), new Point(0,1), new Point(-1,0), new Point(0,-1) }; public static void main(String[] args) { final int[][] islandsMap = buildIslandsMap(); final Queue<Point> firstIslandCoordinates = findFirstIslandEdges(islandsMap); System.out.printf("the minimum required materials for build a bridge are: [%d]\n", calculateMinimumMaterialsForBridge(islandsMap, firstIslandCoordinates)); } private static int calculateMinimumMaterialsForBridge(int[][] islandsMap, Queue<Point> firstIslandCoordinates) { int minRequiredMaterials = -1; final Set<Point> visitedPoints = new HashSet<>(); while(!firstIslandCoordinates.isEmpty()){ int size = firstIslandCoordinates.size(); for(int i = 0; i < size; i++) { Point islandCoordinate = firstIslandCoordinates.poll(); if(islandCoordinate != null && islandsMap[islandCoordinate.getX()][islandCoordinate.getY()] == 1){ return minRequiredMaterials; } if(!visitedPoints.contains(islandCoordinate)){ visitedPoints.add(islandCoordinate); firstIslandCoordinates.addAll(getPossibleRoutesFromPoint(islandCoordinate, islandsMap)); } } minRequiredMaterials++; } return -1; } private static Queue<Point> getPossibleRoutesFromPoint(Point islandCoordinate, int[][] islandsMap) { final Queue<Point> possibleRoutes = new LinkedList<>(); for(Point direction : DIRECTIONS){ Point point = new Point(islandCoordinate.getX() + direction.getX(), islandCoordinate.getY() + direction.getY()); if(point.getX() >= 0 && point.getY() >= 0 && point.getX() < islandsMap.length && point.getY() < islandsMap[point.getX()].length ){ possibleRoutes.add(point); } } return possibleRoutes; } private static Queue<Point> findFirstIslandEdges(int[][] islandsMap) { final Queue<Point> edgePoints = new LinkedList<>(); for (int x = 0; x < islandsMap.length; x++){ for(int y = 0; y < islandsMap[x].length; y++){ if(islandsMap[x][y] == 1) { dfs(islandsMap, x, y, edgePoints); return edgePoints; } } } return edgePoints; } private static void dfs(int[][] islandsMap, int x, int y, final Queue<Point> edgePoints) { if(x < 0 || y < 0 || x >= islandsMap.length || y >= islandsMap[x].length || islandsMap[x][y] == 0){ return; } islandsMap[x][y] = 0; edgePoints.add(new Point(x,y)); for (Point direction : DIRECTIONS){ dfs(islandsMap, x + direction.getX(), y + direction.getY(), edgePoints); } } /** * builds the map with two islands * @return the array with the islands */ private static int[][] buildIslandsMap() { return new int[][] { {0,1,0,0,0,0,0}, {1,1,1,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,0,1,1}, {0,0,0,0,0,1,1}, }; } } ```