Conteo de Islas en Matrices con DFS

¿Qué es el problema número de islas?

El problema "número de islas" es un desafío comúnmente planteado en entrevistas de trabajo de empresas tecnológicas de renombre como Google, Microsoft y Amazon para evaluar habilidades de programación. En esencia, este problema consiste en determinar cuántas "islas" existen en una matriz compuesta por números 1 y 0. En este contexto, el 1 representa la tierra y el 0 el agua. La misión es contar los grupos conectados de tierra, es decir, las islas.

Estrategias para resolver el problema

Resolver este problema requiere una comprensión sólida de búsqueda en profundidad, comúnmente conocida como DFS (Depth First Search). Esta técnica ayuda a identificar cuántas islas hay, navegando a fondo en cada célula de tierra descubierta hasta que se rodee completamente de agua.

¿Cómo se navega en el mapa?

Para abordar el problema, es esencial realizar iteraciones a lo largo de la matriz, explorando cada célula y distinguiendo entre agua y tierra. La lógica parte de un enfoque de búsqueda en profundidad, comenzando desde la primera célula, y extendiéndose a cada célula adyacente que también sea tierra.

¿Cuándo se considera que estamos en una isla?

Una isla se forma solo cuando un conjunto de células de tierra está rodeado por todas partes de agua. Como cada célula de tierra conectada contribuye a una misma isla, es crucial controlar estas conexiones para determinar el límite de cada isla.

¿Cómo implementar una solución con DFS?

Para resolver este problema, una solución efectiva es usar la búsqueda en profundidad (DFS). Este algoritmo permite explorar completamente cada conjunto de tierra, utilizando una función recursiva que se mantiene mientras haya tierra para recorrer.

def numIslands(grid):
    if not grid:
        return 0
    
    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0":
            return
        grid[i][j] = "0"  # Marcar como visitado
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == "1":
                dfs(i, j)
                count += 1  # Incrementar el contador para cada isla encontrada
    return count

Complejidad del algoritmo

La solución mediante DFS tiene una complejidad de tiempo y espacio de (O(n^2)), donde (n) es la dimensión del mapa si se asume que es cuadrado. Esto se debe a que el algoritmo debe explorar cada célula en la cuadrícula para determinar la cantidad de islas, almacenando temporalmente el estado de cada celda en la pila de la recursión.

¡Explora distintas maneras de resolver este problema! Cada enfoque podría ofrecer una perspectiva única sobre estructuras de datos y algoritmos, lo que enriquecerá tu experiencia y habilidades de programación.