Playground: Number of Islands

Cursos Empresas Blog Live Conf Precios

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Playground: Number of Islands

Comentarios

Platzi Team

Estudiante

def numeroDeIslas(mapa):
    if not mapa:
        return 0

    filas = len(mapa)
    columnas = len(mapa[0])
    visitado = [[False] * columnas for _ in range(filas)]

    # 4 direcciones → estándar del problema
    direcciones = [
        (1, 0),   # abajo
        (-1, 0),  # arriba
        (0, 1),   # derecha
        (0, -1),  # izquierda
    ]

    def dfs(i, j):
        # fuera de rango
        if i < 0 or i >= filas or j < 0 or j >= columnas:
            return
        
        # agua o ya visitado
        if mapa[i][j] == "0" or visitado[i][j]:
            return
        
        visitado[i][j] = True

        for dx, dy in direcciones:
            dfs(i + dx, j + dy)

    # contador de islas
    numero_islas = 0

    for i in range(filas):
        for j in range(columnas):
            if mapa[i][j] == "1" and not visitado[i][j]:
                dfs(i, j)
                numero_islas += 1

    return numero_islas

mapa = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"],
]
response = numeroDeIslas(mapa)
print(response)

mapa = [
["1","1","0","0","1"],
["1","1","1","0","1"],
["0","0","1","0","1"],
["0","0","0","0","1"],
["0","0","0","0","1"],
]
response = numeroDeIslas(mapa)
print(response)

John Eduard Meneses González

Estudiante

My solution!!

Hans Uriel Diaz Aguilar

Estudiante

def numeroDeIslas(m):
    visited = set()

    def dfs(r: int,c: int):  
        
        if r < 0 or r >= len(m) or c < 0 or c >= len(m[0]):
            return 0 # Nos protegemos de los bordes 
        if (r,c) in visited or m[r][c] == "0":
            return 0 # Evitamos la repetición
        
        visited.add((r,c))

        dfs(r + 1, c) # Derecha
        dfs(r - 1, c) # Izquierda 
        dfs(r, c - 1) # Arriba
        dfs(r, c + 1) # Abajo

        return 1 # Ya revisamos los 4 lados
        
    total_islas = 0
    for r in range(len(m)):
        for c in range(len(m[0])):
            total_islas += dfs(r, c)

    return total_islas

Andres Silva Vega

Estudiante

def numeroDeIslas(mapa):
   # Tu código aquí 👇
   numero_islas = 0
   for i, row in enumerate(mapa):
      for j, item in enumerate(row):
         if item == "1":
            numero_islas += dfs(i, j, mapa)
   return numero_islas
def dfs(i, j, mapa) :
   mapa[i][j] = "2"
   if j+1 < len(mapa[i]) and mapa[i][j+1] == "1":
      dfs(i, j+1, mapa)
   if i+1 < len(mapa) and mapa[i+1][j] == "1":
      dfs(i+1, j, mapa)
   if j-1 >= 0  and mapa[i][j-1] == "1":
      dfs(i, j-1, mapa)
   if i-1 >= 0 and mapa[i-1][j] == "1":
      dfs(i-1, j, mapa)
   return 1

Miguel Angel Reyes Moreno

Estudiante

Comparto mi solución en Python:

from typing import List

class Solution:  def numIslands(self, grid: List\[List\[str]]) -> int:    islands\_counter = 0    def DFS(i, j):      if grid\[i]\[j] == '0':        return
&#x20;     grid\[i]\[j] = '0'      # go up      if i -1 >= 0:        DFS(i-1, j)      # go down      if i + 1 < len(grid):        DFS(i+1, j)      # go left      if j - 1 >= 0:        DFS(i, j-1)      # go right      if j + 1 < len(grid\[i]):        DFS(i, j+1)

&#x20;   if grid is None or not grid:      return 0
&#x20;   for i in range(len(grid)):      for j in range(len(grid\[i])):        if grid\[i]\[j] == '1':          DFS(i,j)          islands\_counter += 1
&#x20;   return islands\_counter

if \_\_name\_\_ == "\_\_main\_\_":    solution = Solution()  # Instantiate the Solution class
&#x20;   \# Example 1    grid1 = \[      \["1","1","1","1","0"],      \["1","1","0","1","0"],      \["1","1","0","0","0"],      \["0","0","0","0","0"]    ]    print("Number of islands in grid1: ", solution.numIslands(grid1))
&#x20;   \# Example 2    grid2 = \[      \["1","1","0","0","0"],      \["1","1","0","0","0"],      \["0","0","1","0","0"],      \["0","0","0","1","1"]    ]    print("Number of islands in grid2: ", solution.numIslands(grid2))
&#x20;   \# Example 3 - Edge case (empty grid)    grid3 = \[]    print("Number of islands in grid3: ", solution.numIslands(grid3))
&#x20;   \# Example 4 - Edge case (all water)    grid4 = \[      \["0","0","0","0"],      \["0","0","0","0"]    ]    print("Number of islands in grid4: ", solution.numIslands(grid4))

Daniel Barreto

Estudiante

def map_island(island_pos, mapa, searched):
   stack = [island_pos]
   while stack:
      current_pos = stack.pop()
      if(not current_pos in searched):
         searched.append(current_pos)
      adjeisent = [
         [current_pos[0] + 1, current_pos[1]],
         [current_pos[0] - 1, current_pos[1]],
         [current_pos[0], current_pos[1] + 1],
         [current_pos[0], current_pos[1] - 1]
      ]
      for position in adjeisent:
         if(not position in searched and
            position[0] < len(mapa) and
            position[0] > -1 and
            position[1] < len(mapa[0]) and
            position[1] > -1 and
            mapa[position[0]][position[1]] == "1"
         ):
            stack.append(position)

def numeroDeIslas(mapa):
   # Tu código aquí 👇
   islands = 0
   stack = [[0,0]]
   searched = []
   for i in range(0, len(mapa)):
      for j in range(0, len(mapa[0])):
         current_pos = [i, j]
         if(mapa[current_pos[0]][current_pos[1]] == "1" and
            not current_pos in searched
         ):
            islands += 1
            map_island(current_pos, mapa, searched)
         searched.append(current_pos)

   return islands
```Mi solución, sin usar recursión :)

Ivan Scaglioni

Estudiante

Mi solución:


def numeroDeIslas(mapa):
   # Tu código aquí 👇
   filas = len(mapa)
   if filas > 0:
        columnas = len(mapa[0]) 

   """ Primera parte encontrar las cooedernas de todos los "1" en el mapa """
   coordenadas=[(1,1)]
   coordenadas.pop()
   index_x = 0
   for x in mapa:
      index_y =0
      for y in x:
         if y == "1":
            coordenadas.append((index_x, index_y))
         index_y += 1
      index_x += 1

   """ segunda parte encontrar la cantidad de islas en el mapa"""

   count_islands = 0



   for island in coordenadas:
      current_island = [island]
      x = island[0]
      y = island[1]
      if mapa[x][y] == "0":
         continue
      else:
         print(x,y)
         count_islands += 1
      for  here   in current_island:
         x  = here[0]
         y = here[1] 
         mapa[x][y] = "0"

         """up"""
         if  y+1 < columnas:
            if mapa[x][y+1] == "1":
               current_island.append((x,y+1))


         """rigth"""
         if x+1 < filas:
            if mapa[x+1][y] == "1":
               current_island.append((x+1,y))


         """down"""
         if y-1 >= 0:
            if mapa[x][y-1] == "1":
               current_island.append((x,y-1))


         """left"""
         if x-1 >= 0:
            if mapa[x-1][y] == "1":
               current_island.append((x-1,y))


   return count_islands

def numeroDeIslas(mapa):
    if not mapa:
        return 0

    filas = len(mapa)
    columnas = len(mapa[0])
    visitado = [[False] * columnas for _ in range(filas)]

    # 4 direcciones → estándar del problema
    direcciones = [
        (1, 0),   # abajo
        (-1, 0),  # arriba
        (0, 1),   # derecha
        (0, -1),  # izquierda
    ]

    def dfs(i, j):
        # fuera de rango
        if i < 0 or i >= filas or j < 0 or j >= columnas:
            return
        
        # agua o ya visitado
        if mapa[i][j] == "0" or visitado[i][j]:
            return
        
        visitado[i][j] = True

        for dx, dy in direcciones:
            dfs(i + dx, j + dy)

    # contador de islas
    numero_islas = 0

    for i in range(filas):
        for j in range(columnas):
            if mapa[i][j] == "1" and not visitado[i][j]:
                dfs(i, j)
                numero_islas += 1

    return numero_islas

mapa = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"],
]
response = numeroDeIslas(mapa)
print(response)

mapa = [
["1","1","0","0","1"],
["1","1","1","0","1"],
["0","0","1","0","1"],
["0","0","0","0","1"],
["0","0","0","0","1"],
]
response = numeroDeIslas(mapa)
print(response)

def numeroDeIslas(m):
    visited = set()

    def dfs(r: int,c: int):  
        
        if r < 0 or r >= len(m) or c < 0 or c >= len(m[0]):
            return 0 # Nos protegemos de los bordes 
        if (r,c) in visited or m[r][c] == "0":
            return 0 # Evitamos la repetición
        
        visited.add((r,c))

        dfs(r + 1, c) # Derecha
        dfs(r - 1, c) # Izquierda 
        dfs(r, c - 1) # Arriba
        dfs(r, c + 1) # Abajo

        return 1 # Ya revisamos los 4 lados
        
    total_islas = 0
    for r in range(len(m)):
        for c in range(len(m[0])):
            total_islas += dfs(r, c)

    return total_islas

def numeroDeIslas(mapa):
   # Tu código aquí 👇
   numero_islas = 0
   for i, row in enumerate(mapa):
      for j, item in enumerate(row):
         if item == "1":
            numero_islas += dfs(i, j, mapa)
   return numero_islas
def dfs(i, j, mapa) :
   mapa[i][j] = "2"
   if j+1 < len(mapa[i]) and mapa[i][j+1] == "1":
      dfs(i, j+1, mapa)
   if i+1 < len(mapa) and mapa[i+1][j] == "1":
      dfs(i+1, j, mapa)
   if j-1 >= 0  and mapa[i][j-1] == "1":
      dfs(i, j-1, mapa)
   if i-1 >= 0 and mapa[i-1][j] == "1":
      dfs(i-1, j, mapa)
   return 1

from typing import List

class Solution:  def numIslands(self, grid: List\[List\[str]]) -> int:    islands\_counter = 0    def DFS(i, j):      if grid\[i]\[j] == '0':        return
&#x20;     grid\[i]\[j] = '0'      # go up      if i -1 >= 0:        DFS(i-1, j)      # go down      if i + 1 < len(grid):        DFS(i+1, j)      # go left      if j - 1 >= 0:        DFS(i, j-1)      # go right      if j + 1 < len(grid\[i]):        DFS(i, j+1)

&#x20;   if grid is None or not grid:      return 0
&#x20;   for i in range(len(grid)):      for j in range(len(grid\[i])):        if grid\[i]\[j] == '1':          DFS(i,j)          islands\_counter += 1
&#x20;   return islands\_counter

if \_\_name\_\_ == "\_\_main\_\_":    solution = Solution()  # Instantiate the Solution class
&#x20;   \# Example 1    grid1 = \[      \["1","1","1","1","0"],      \["1","1","0","1","0"],      \["1","1","0","0","0"],      \["0","0","0","0","0"]    ]    print("Number of islands in grid1: ", solution.numIslands(grid1))
&#x20;   \# Example 2    grid2 = \[      \["1","1","0","0","0"],      \["1","1","0","0","0"],      \["0","0","1","0","0"],      \["0","0","0","1","1"]    ]    print("Number of islands in grid2: ", solution.numIslands(grid2))
&#x20;   \# Example 3 - Edge case (empty grid)    grid3 = \[]    print("Number of islands in grid3: ", solution.numIslands(grid3))
&#x20;   \# Example 4 - Edge case (all water)    grid4 = \[      \["0","0","0","0"],      \["0","0","0","0"]    ]    print("Number of islands in grid4: ", solution.numIslands(grid4))

def map_island(island_pos, mapa, searched):
   stack = [island_pos]
   while stack:
      current_pos = stack.pop()
      if(not current_pos in searched):
         searched.append(current_pos)
      adjeisent = [
         [current_pos[0] + 1, current_pos[1]],
         [current_pos[0] - 1, current_pos[1]],
         [current_pos[0], current_pos[1] + 1],
         [current_pos[0], current_pos[1] - 1]
      ]
      for position in adjeisent:
         if(not position in searched and
            position[0] < len(mapa) and
            position[0] > -1 and
            position[1] < len(mapa[0]) and
            position[1] > -1 and
            mapa[position[0]][position[1]] == "1"
         ):
            stack.append(position)

def numeroDeIslas(mapa):
   # Tu código aquí 👇
   islands = 0
   stack = [[0,0]]
   searched = []
   for i in range(0, len(mapa)):
      for j in range(0, len(mapa[0])):
         current_pos = [i, j]
         if(mapa[current_pos[0]][current_pos[1]] == "1" and
            not current_pos in searched
         ):
            islands += 1
            map_island(current_pos, mapa, searched)
         searched.append(current_pos)

   return islands
```Mi solución, sin usar recursión :)

def numeroDeIslas(mapa):
   # Tu código aquí 👇
   filas = len(mapa)
   if filas > 0:
        columnas = len(mapa[0]) 

   """ Primera parte encontrar las cooedernas de todos los "1" en el mapa """
   coordenadas=[(1,1)]
   coordenadas.pop()
   index_x = 0
   for x in mapa:
      index_y =0
      for y in x:
         if y == "1":
            coordenadas.append((index_x, index_y))
         index_y += 1
      index_x += 1

   """ segunda parte encontrar la cantidad de islas en el mapa"""

   count_islands = 0



   for island in coordenadas:
      current_island = [island]
      x = island[0]
      y = island[1]
      if mapa[x][y] == "0":
         continue
      else:
         print(x,y)
         count_islands += 1
      for  here   in current_island:
         x  = here[0]
         y = here[1] 
         mapa[x][y] = "0"

         """up"""
         if  y+1 < columnas:
            if mapa[x][y+1] == "1":
               current_island.append((x,y+1))


         """rigth"""
         if x+1 < filas:
            if mapa[x+1][y] == "1":
               current_island.append((x+1,y))


         """down"""
         if y-1 >= 0:
            if mapa[x][y-1] == "1":
               current_island.append((x,y-1))


         """left"""
         if x-1 >= 0:
            if mapa[x-1][y] == "1":
               current_island.append((x-1,y))


   return count_islands

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

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

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

Inorder, Preorder y Postorder en árboles

Suma de caminos raíz a hoja en árboles

Suma de caminos raíz a hoja con DFS

Playground: Sum Root to Leaf Numbers

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

Número de islas con DFS en matrices

Problema de islas resuelto con DFS

Playground: Number of Islands

Número de islas con DFS recursivo en Python

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

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

BFS

Cómo BFS recorre grafos por niveles

Implementación de BFS con colas en Python

Mínimos movimientos del caballo en ajedrez

Minimum Knight's Move con BFS

Playground: Minimum Knights Moves

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

Propagación BFS en Rotting Oranges

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Implementación de BFS para naranjas podridas

Puente más corto entre islas con BFS

Shortest Bridge: combina DFS y BFS

Playground: Shortest Bridge Between Islands

Shortest Bridge con DFS y BFS en Python

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

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

Backtrack

Backtracking para encontrar soluciones válidas

Combinaciones de letras en teclado telefónico

Combinaciones de teclado con backtracking

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

Playground: Letter Combinations of a Phone Number

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

Backtracking para generar IPs válidas

Playground: Restore IP Addresses

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

Word Search con DFS y backtracking

Playgrund: Word Search

Búsqueda de palabras en matrices con DFS

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Dijkstra y topological sort en grafos

Qué sigue después de aprender grafos