Introducción

1

¿Qué es un grafo?

2

¿Qué es un árbol?

3

¿Qué es recursión?

4

Aplicaciones reales de grafos y árboles

5

Formas de representar un grafo

DFS

6

Análisis de DFS: algoritmo de búsqueda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un Árbol

10

Sum Root to Leaf Numbers: análisis del problema

11

Solución de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: análisis del problema

15

Solución de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

Análisis de BFS: algoritmo de búsqueda en anchura

21

Programando BFS con Python

22

Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema

23

Solución de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: análisis del problema

27

Solución de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: análisis del problema

31

Solución de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

Letter Combinations of a Phone Number: análisis del problema

38

Solución de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: análisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: análisis del problema

45

Solución de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Próximos pasos

51

¿Qué otros algoritmos y tipos de grafos puedes aprender?

52

¿Quieres más cursos avanzados de algoritmos?

No tienes acceso a esta clase

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

Number of Islands: análisis del problema

14/52
Recursos

¿Qué es el problema "Número de Islas"?

El problema del "Número de Islas" es un desafío comúnmente presentado en entrevistas de trabajo en grandes empresas de tecnología, como Google, Microsoft y Facebook. El objetivo es analizar una matriz binaria de dimensiones m por n, donde los valores son únicamente 1 y 0. Un '1' representa tierra y un '0' representa agua. La tarea es determinar cuántas islas existen en este mapa, donde una isla está definida por tierra conectada adyacente y rodeada de agua.

¿Cómo se definen las islas en la matriz?

  • Isla: Un conjunto de tierras conectadas adyacentes rodeado por agua.
  • Adjacencia: La conexión puede ser horizontal o vertical entre casillas.
  • Suposición adicional: Los bordes de la cuadrícula están rodeados de agua, por ejemplo, si una isla toca la esquina, podemos asumir que hay agua alrededor.

Este problema plantea un desafío de cálculo eficiente, especialmente cuando la matriz crece en tamaño, como sería el caso de un mapa del mundo.

¿Cómo abordar este problema?

Análisis de la matriz como humano

A simple vista, podemos identificar visualmente islas en una matriz pequeña. Sin embargo, cuando los datos son extensos, la identificación manual se complica y es necesario el uso de algoritmos para resolverlo eficazmente.

Una solución propuesta: DFS

Un enfoque algorítmico para resolver este problema es mediante el algoritmo DFS (Depth First Search). DFS es una técnica bien conocida para explorar y contar componentes conectados en un grafo, que en este contexto son las islas formadas por las tierras conectadas.

Pasos generales de DFS para el problema:

  1. Recorrer la matriz: Utilizar un doble bucle para recorrer cada celda de la matriz.
  2. Iniciar búsqueda DFS: Al encontrar un '1', iniciar la búsqueda DFS para marcar todas las partes de la isla conectada.
  3. Marcar la visita: Cambiar los '1' visitados a un nuevo valor para indicar que esa porción ya fue procesada.
  4. Contar islas: Incrementar un contador cada vez que se inicia una nueva búsqueda DFS desde un '1'.

Este enfoque garantiza que cada porción de la isla se procesará una única vez, logrando eficiencia en el algoritmo.

¿Cómo puedes encontrar tu propia solución?

Aunque DFS es una opción eficiente, este problema permite varias aproximaciones. Se invita a los participantes a desarrollar ideas propias, documentar su proceso y compartir en una comunidad de aprendizaje. La diversidad de soluciones puede enriquecer el entendimiento colectivo y abre la puerta a metodologías alternativas.

Consejos prácticos

  • Participación activa: Documenta y comparte posibles soluciones, aunque no las hayas implementado, en espacios comunitarios de aprendizaje.
  • Aprende de otros: Revisa y comenta las soluciones de tus compañeros, esto fomenta la discusión y el entendimiento compartido.
  • Experimentación: Explora y experimenta con distintos enfoques algorítmicos que podrían optimizar la solución dependiendo del caso de uso.

El dominio de este tipo de problema puede ser un excelente diferenciador en procesos de selección para roles técnicos. Además, la práctica constante de algoritmos refuerza las habilidades necesarias para desafíos avanzados en ciencias de la computación. ¡Sigue aprendiendo y explorando nuevas soluciones!

Aportes 6

Preguntas 0

Ordenar por:

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

< # Lees dos enteros, n y m, que representan las dimensiones de la matriz
n = int(input())
m = int(input())

# Creas una matriz llamada "matrix" para almacenar los valores binarios
matrix = []

# Llenas la matriz leyendo las filas de la entrada estándar
for __ in range(0, n):
    a = input().split()  # Lees una línea y la divides en números
    b = [int(i) for i in a]  # Conviertes los números a enteros
    matrix.append(b)  # Agregas la fila a la matriz

# Definición de la función dfs (Depth-First Search)
def dfs(matrix, node, visited):
    # Marca el nodo actual como visitado y lo establece en 0 en la matriz
    visited[(node[0], node[1])] = True
    matrix[node[0]][node[1]] = 0

    # Explora las celdas vecinas en las cuatro direcciones: arriba, abajo, derecha e izquierda
    # Si una celda vecina contiene un 1 y no ha sido visitada, llama recursivamente a dfs
    # para explorar esa celda vecina

    # Arriba
    if node[0] - 1 >= 0 and matrix[node[0] - 1][node[1]] == 1 and (node[0] - 1, node[1]) not in visited:
        dfs(matrix, [node[0] - 1, node[1]], visited)

    # Abajo
    if node[0] + 1 < n and matrix[node[0] + 1][node[1]] == 1 and (node[0] + 1, node[1]) not in visited:
        dfs(matrix, [node[0] + 1, node[1]], visited)

    # Derecha
    if node[1] + 1 < m and matrix[node[0]][node[1] + 1] == 1 and (node[0], node[1] + 1) not in visited:
        dfs(matrix, [node[0], node[1] + 1], visited)

    # Izquierda
    if node[1] - 1 >= 0 and matrix[node[0]][node[1] - 1] == 1 and (node[0], node[1] - 1) not in visited:
        dfs(matrix, [node[0], node[1] - 1], visited)

# Inicializas un diccionario "visited" para realizar un seguimiento de las celdas visitadas
visited = {}

# Inicializas una variable "a" para contar el número de componentes conexas
a = 0

# Recorres todas las celdas de la matriz
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            # Si encuentras una celda con un 1, incrementas el contador "a" y llamas a dfs
            a += 1
            dfs(matrix, (i, j), visited)

# Imprimes el número total de componentes conexas
print(a)

> 
FUNCIÓN num\_islands(grid): inicializar contador = 0 para cada fila i: para cada columna j: si grid\[i]\[j] == '1': llamar dfs(i, j) incrementar contador retornar contador FUNCIÓN dfs(i, j): si i o j fuera de rango o grid\[i]\[j] ≠ '1': retornar marcar grid\[i]\[j] como '0' (visitado) llamar dfs(i+1, j) (abajo) llamar dfs(i-1, j) (arriba) llamar dfs(i, j+1) (derecha) llamar dfs(i, j-1) (izquierda)

Hola 😄, podría empezar a hacer una búsqueda recursiva de la siguiente manera:
.

.
Entrar en una casilla, lo primero que hago es marcar la casilla con un # y luego buscar en las 4 direcciones recursivamente.
.
Si la casilla es 0 o # significa que hay agua o ya he pasado por ahí. Si es 1 sigo buscando.
.
Cuando encuentre que las cuatro direcciones son 0 significa que hay una isla, entonces aumento mi contador de islas, que por comodidad lo tendría global.
.

.
Al final mi matriz quedaría de la siguiente manera:
.

.
Significaría que ya he terminado de buscar islas.

Este es probelma con el que se eseña bfs, en la uva hay un problema para ponerlo en practica 11094 - Continents

Mi solución

def scan_for_near_islands(row, column, matrix, checked_stack):
    for pos in [(row-1, column),(row,column+1),(row+1, column),(row, column-1)]:
        if pos not in checked_stack:
            checked_stack.append(pos)
            try:
                if matrix[pos[0]][pos[1]] == 1:
                    scan_for_near_islands(pos[0], pos[1], matrix, checked_stack)
            except IndexError:
                pass

def find_islands_in_matrix(matrix, checked_stack = []):
    total_island_sum = 0
    for row, column in zip(range(len(matrix)),range(len(matrix[0]))):
        if (row, column) not in checked_stack:
            checked_stack.append((row, column))
            if matrix[row][column] == 1:
                scan_for_near_islands(row, column, matrix, checked_stack)
                total_island_sum += 1
        
    return total_island_sum
\# 5 def num\_islands(grid): \# 6 count = 0 \# 7 for i in range(len(grid)): for j in range(len(grid\[0])): if grid\[i]\[j] == '1': dfs(i, j) count += 1 \# 8 return count \# 1 def dfs(i, j): \# 2 if i < 0 or i >= len(grid) or j < 0 or j >= len(grid\[0]) or grid\[i]\[j] != '1': return \# 3 grid\[i]\[j] = '0' \# 4 dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1)