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

Clase 14 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

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

Recorrer la matriz: Utilizar un doble bucle para recorrer cada celda de la matriz.
Iniciar búsqueda DFS: Al encontrar un '1', iniciar la búsqueda DFS para marcar todas las partes de la isla conectada.
Marcar la visita: Cambiar los '1' visitados a un nuevo valor para indicar que esa porción ya fue procesada.
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!

Harold Zurita Simon

student•

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.

Gabriel Cavedal

student•

1) inizializar: visitados => una matriz n x m de booleanos islas => contador de islas

2) iterar la matriz mapa hasta encontrar tierra ('1').

3) aplicar dfs tomando el primer '1' como nodo raíz, marcando los visitados.

4) al finalizar el dfs islas += islas

5) continuar iterando por no visitados hasta encontrar más tierra.

al final islas tiene el resultado deseado.

Santiago García Rincón

student•

< # 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)

>

Miguel Angel Otero Otero

student•

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)

Carlos Raúl Romero Martínez

student•

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

EDSEL Laucho Di Meo

student•

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

Miguel Angel Otero Otero

student•

# 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)