Cursos Empresas Blog Live Conf Eventos Precios

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

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Ejercicios resueltos de DFS

Reemplazar un Color en una Sección de la Imagen Una imagen está representada por una cuadrícula de enteros m x n donde image[i][j] representa el valor de los píxeles de la imagen.

También se le dan tres enteros sr, sc y color. Debe realizar un relleno en la imagen comenzando por el píxel image[sr][sc].

Para realizar un relleno, considere el píxel inicial, más cualquier píxel conectado en 4 direcciones al píxel inicial del mismo color que el píxel inicial, más cualquier píxel conectado en 4 direcciones a esos píxeles (también con el mismo color), y así sucesivamente. Reemplazar el color de todos los píxeles mencionados por el color.

Devuelve la imagen modificada después de realizar el relleno.

Ejemplo 1: Entrada: imagen = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Salida: [[2,2,2],[2,2,0],[2,0,1]] Explicación: Desde el centro de la imagen con posición (sr, sc) = (1, 1) (es decir, el píxel rojo), todos los píxeles conectados por un camino del mismo color que el píxel inicial (es decir, los píxeles azules) se colorean con el nuevo color. Observe que la esquina inferior no se colorea con el color 2, porque no está conectada en 4 direcciones al píxel inicial.

Ejemplo 2: Entrada: imagen = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Salida: [[0,0,0],[0,0,0]] Explicación: El píxel inicial ya tiene el color 0, por lo que no se realizan cambios en la imagen.

def colorearSector(self, imagen: List[List[int]], sr: int, sc: int, nuevoColor: int) -> List[List[int]]:
   if not imagen or not imagen[0]:
       return imagen
   if imagen[sr][sc] == nuevoColor:
       return imagen
  
   def dfs(imagen, i, j,colorActual):
       imagen[i][j] = nuevoColor           
       for x, y in direcciones:
           if 0 <= x+i < len(imagen) and 0 <= j+y < len(imagen[0]) and imagen[x+i][j+y ] == colorActual:
               dfs(imagen, x+i, j+y,  colorActual)
   direcciones = [[1,0],[0,1],[-1,0],[0,-1]]    
   dfs(imagen, sr, sc, imagen[sr][sc])
   return imagen

Construir una cadena a partir de un árbol binario Dada la raíz de un árbol binario, construya una cadena formada por paréntesis y enteros a partir de un árbol binario con el modo de recorrido de preorden, y devuélvala. Omita todos los pares de paréntesis vacíos que no afecten a la relación de mapeo uno a uno entre la cadena y el árbol binario original.

Ejemplo 1 Entrada: raíz = [1,2,3,4] Salida: "1(2(4))(3)" Explicación: Originalmente, tiene que ser "1(2(4)())(3()())", pero hay que omitir todos los pares de paréntesis vacíos innecesarios. Y será "1(2(4))(3)"

Ejemplo 2: Entrada: raíz = [1,2,3,null,4] Salida: "1(2()(4))(3)" Explicación: Casi lo mismo que el primer ejemplo, excepto que no podemos omitir el primer par de paréntesis para romper la relación de mapeo uno a uno entre la entrada y la salida.

# class TreeNode:
#     def __init__(self, val=0, izquierda=None, derecha=None):
#         self.val = val
#         self.izquierda = izquierda
#         self.derecha = derecha
class Solution:
   def tree2str(self, t: TreeNode) -> str:
       def dfs(raiz):
           if not raiz: return ''
           string = str(raiz.val)
           if not raiz.izquierda and not raiz.derecha:
               return string
           string += '(' + str(dfs(raiz.izquierda)) + ')'
           if raiz.derecha:
               string += '(' + str(dfs(raiz.derecha)) + ')'
           return string
       return dfs(t)

Ancestro común más bajo de un árbol binario Dado un árbol binario, encuentre el ancestro común más bajo (LCA) de dos nodos dados en el árbol. Según la definición de LCA en Wikipedia "El mínimo común antecesor se define entre dos nodos p y q como el nodo más bajo de T que tiene tanto p como q como descendientes (donde permitimos que un nodo sea descendiente de sí mismo)."

Ejemplo 1: Entrada: raíz = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Salida: 3 Explicación: El ACV de los nodos 5 y 1 es 3.

Ejemplo 2: Entrada: raíz = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Salida: 5 Explicación: El LCA de los nodos 5 y 4 es 5, ya que un nodo puede ser descendiente de sí mismo según la definición de ACV. Ejemplo 3: Entrada: raíz = [1,2], p = 1, q = 2 Salida: 1

def LCA(self, raiz: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
   if not raiz or raiz == p or raiz == q:
       return raiz
   izquierda = self.LCA(raiz.izquierda,p,q)
   derecha = self.LCA(raiz.derecha,p,q)
   if izquierda and derecha:
       return raiz
   return izquierda or derecha

Batalla Naval - Contar Barcos Dado un tablero de m x n donde cada celda es un acorazado 'X' o un vacío '.', devuelva el número de los barcos en el tablero. Los barcos sólo pueden colocarse horizontal o verticalmente en el tablero. En otras palabras, sólo pueden tener la forma 1 x k (1 fila, k columnas) o k x 1 (k filas, 1 columna), donde k puede ser de cualquier tamaño. Al menos una celda horizontal o vertical separa dos barcos (es decir, no hay barcos adyacentes).

Ejemplo 1: Entrada: tablero = [["X",".",".", "X"],[".",".", "X"],[".",".", "X"] Salida: 2

Ejemplo 2: Entrada: tablero = [["."]] Salida: 0

def countBattleships(self, tablero: List[List[str]]) -> int:
   def dfs(i,j):
       if 0 <= i < len(tablero) and 0 <= j < len(tablero[0]) and tablero[i][j] == 'X':
           tablero[i][j] = '.'
           dfs(i+1,j)
           dfs(i-1,j)
           dfs(i,j-1)
           dfs(i,j+1)
   cantidad = 0
   for i in range(len(tablero)):
       for j in range(len(tablero[0])):
           if tablero[i][j] == 'X':
               dfs(i,j)
               cantidad+=1
   return cantidad

Número de Islas Cerradas Dada una cuadrícula 2D formada por 0s (tierra) y 1s (agua). Una isla es un grupo máximo de 0s conectado en 4 direcciones y una isla cerrada es una isla totalmente (toda a la izquierda, arriba, derecha, abajo) rodeada de 1s. Devuelve el número de islas cerradas.

Ejemplo 1: Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Salida: 2 Explicación: Las islas en gris están cerradas porque están completamente rodeadas de agua (grupo de 1s).

def closedIsland(self, mapa: List[List[int]]) -> int:
   if len(mapa) == 0: return 0
   def dfs(i,j):
       if not(0<=i<len(mapa) and 0<=j<len(mapa[0])): 
           return False
       if mapa[i][j] == 1:
           return True
       mapa[i][j] = 1
       A = dfs(i+1,j)
       B = dfs(i-1,j)
       C = dfs(i,j+1)
       D = dfs(i,j-1)
       return A and B and C and D
 
   cantidad = 0
   for i in range(len(mapa)):
       for j in range(len(mapa[0])):
           if mapa[i][j] == 0 and dfs(i,j):
               cantidad += 1
   return cantidad

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

Comentarios4

Diego Portillo

Estudiante

Hace 7 meses•editado

Solution Exercise 4:


input_1 =  [
    ["X",".", "X"],
    ["X",".", "X"],
    ["X",".", "X"]
]
output_1 = 2
input_2 = [["."]]
output_2 = 0
def count_ships(table):
    count = 0
    for i in range(len(table)):
        for j in range(len(table[i])):
            if table[i][j] == 'X':
                count += 1
                stack = [(i, j)]
                while stack:
                    r, c = stack.pop()
                    if 0 <= r < len(table) and 0 <= c < len(table[r]) and table[r][c] == 'X':
                        table[r][c] = 'o'
                        stack.append((r+1,c))
                        stack.append((r, c+1))
                        
    return count
print(count_ships(input_1) == output_1)
print(count_ships(input_2) == output_2)

Comparison with teacher's solution:

Both solutions use the same core strategy: flood-fill to mark visited cells and count connected components. Here are the key differences:

Recursion vs Iteration

The first solution uses recursive DFS, which is elegant but risks a stack overflow on very large boards. The second uses an explicit stack (iterative DFS), which is safer and generally preferred in production.

Directional exploration

The first solution explores all 4 directions (up, down, left, right). The second only explores down and right — this works here because ships can't be adjacent, so you'll never miss a cell by skipping up/left (they'd already be marked). It's a clever optimization, though it's less obvious to readers.

Visited marker

Both mutate the input board. The first replaces 'X' with '.', while the second uses 'o'. Using 'o' is slightly better for debugging since it distinguishes "visited ship cell" from "originally empty cell", but neither approach is ideal if you need the original board preserved after the call.

Bounds checking

The first solution checks bounds inside dfs before accessing the cell, which is safe. The second pushes neighbors onto the stack unconditionally and checks bounds when popping — also correct, just does a bit of extra work pushing out-of-bounds coordinates.

Overall verdict

The second solution is slightly better engineered (no recursion limit risk, optimized directions), but the first is more readable and general. If the constraint that ships are never adjacent were removed, the second solution would break — so the first is more robust to changing requirements.

A small improvement worth noting for the second: since you only push (r+1, c) and (r, c+1), you can also drop the bounds check on r-1/c-1 entirely, but you should document why you only need two directions so future readers aren't confused.

Diego Portillo

Estudiante

Hace 7 meses•editado

Solution Exercise 5:


input = [
    [1, 1, 1, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 1, 1, 1, 0],
    [1, 0, 1, 0, 1, 1, 1, 0],
    [1, 0, 0, 0, 0, 1, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 0],
]
output = 1
def count_closed_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] != 0:  # 0 = land (island)
                continue
            # Explore this island (connected 0s) with BFS
            stack = [(i, j)]
            touches_border = False
            while stack:
                r, c = stack.pop()
                if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 0:
                    continue
                grid[r][c] = 2  # visited
                if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
                    touches_border = True
                stack.append((r + 1, c))
                stack.append((r - 1, c))
                stack.append((r, c + 1))
                stack.append((r, c - 1))
            # Count only if the island never touched the border (fully surrounded by water/1s)
            if not touches_border:
                count += 1
    return count
print(count_closed_islands(input) == output)

Comparison with teacher's exercise:

Core strategy difference — this is the key insight

The first solution asks "is every path from this cell blocked by water?" by propagating True/False up through the recursion. The second asks "does this island ever touch the border?" — a fundamentally different framing that's arguably more intuitive.

The subtle bug in solution 1

python

A = dfs(i+1,j)
B = dfs(i-1,j)
C = dfs(i,j+1)
D = dfs(i,j-1)
return A and B and C and D

Because Python evaluates all four calls before the and (they're assigned to variables first), the full island always gets marked as visited regardless of whether it's closed. This is actually intentional and necessary — if you used short-circuit and directly, you'd stop exploring early and leave unvisited 0s that would be counted again later. It's correct, but it's a subtle trap that makes the code harder to reason about at first glance.

Solution 2 is cleaner in its logic

Marking visited cells as 2 (instead of 1) is a nice touch — it clearly separates "water", "unvisited land", and "visited land". The border-touch flag is easy to follow and the iterative approach avoids recursion depth issues.

One inefficiency in solution 2

It pushes all 4 neighbors onto the stack before checking bounds/visited status, doing the check only on pop. This is correct but does extra work. A minor point.

Verdict

Solution 2 wins on clarity and safety. The border-touching approach is a well-known pattern for this problem class and makes the intent obvious. Solution 1's trick of storing all DFS results in variables to prevent short-circuiting is clever but fragile — someone refactoring it to return dfs(...) and dfs(...) and dfs(...) and dfs(...) would silently introduce a bug.

Diego Portillo

Estudiante

Hace 7 meses•editado

Solution Exercise 2:


example_1 = [1,2,3,4]
example_2 = [1,2,3,None,4]
output_1 = "1(2(4))(3)"
output_2 = "1(2()(4))(3)"
def parentheses_concat(array):
    def depth_first_search_recursive(index):
        # this is to limit the recursion to the number of elements in the array
        if index >= len(array) or array[index] is None:
            return ""
        
        # this is to follow the nodes in the order of the array input
        left_index = 2*index + 1
        right_index = 2*index + 2
        left = depth_first_search_recursive(left_index)
        right = depth_first_search_recursive(right_index)
        # if this is a leaf, return the value only
        if left == ''  and right  =='':
            return str(array[index])
        
        # if left doesn't exists we have to keep an empty pair of parentheses
        if left == '':
            return str(array[index]) + "()" + "(" + right + ")"
        
        # if only left exists is not necessary to have the empty parentheses
        if right == '':
            return str(array[index]) + "(" + left + ")"
        
        # if both exists put the parent node with each child in parenthesis
        return str(array[index]) + "(" + left + ")(" + right + ")"
    
    # go throught the input array starting from the index 0
    return depth_first_search_recursive(0)
print(parentheses_concat(example_1) == output_1)
print(parentheses_concat(example_2) == output_2)

Comparision with teacher's solution:

these two are also solving the same problem (build a parenthesis string from a binary tree using preorder DFS), but again the model of the data structure is completely different, and that changes why the code looks the way it does.

🌳 1. Data Representation (This is the BIG difference)

🔹 First one: parentheses_concat(array)

Your tree is stored as a flat array:

array = [1,2,3,None,4]

And you simulate a tree using index math:

left_index  = 2*i + 1right_index = 2*i + 2

So:

The "tree" does not exist explicitly — you infer it from positions.

This is like how heaps are stored.

🔹 Second one: tree2str(self, t: TreeNode)

Here the tree is an actual linked structure:

raiz.izquierdaraiz.derecha

So:

The tree exists as connected objects (nodes pointing to nodes).

No index math needed.

🧠 2. Why the logic is different

Look at this in your array version:

if index >= len(array) or array[index] is None:    return ""

You must do this because:

Arrays may contain None
The "tree shape" is implicit
Some children don’t exist physically
You can accidentally "walk" into invalid indexes

So you're constantly asking:

"Does this node really exist?"

In the TreeNode version:

if not raiz:    return ''

That's enough — because:

Missing children are literally None
The structure already encodes validity

So traversal becomes cleaner.

⚙️ 3. Parenthesis rule difference

Both must respect this rule:

If a node has a right child but no left child → you MUST add ()

Example:

    1     \      2

Must be:

1()(2)

Array version must detect this manually:

if left == '':    return val + "()" + "(" + right + ")"

Because "missing left child" is ambiguous in arrays.

Node version is more natural:

string += '(' + dfs(raiz.izquierda) + ')'if raiz.derecha:    string += '(' + dfs(raiz.derecha) + ')'

Calling dfs(None) returns '' → automatically gives "()"

🏁 4. Is one better?

FeatureArray versionTreeNode version

Readability

❌ Harder

✅ Cleaner

Performance

⚖️ Similar

Safety

❌ Index errors possible

✅ Pointer-safe

Matches real tree?

❌ No

✅ Yes

Interview standard

❌ Rare

✅ Expected

🚨 Important

In interviews / LeetCode-style problems, the expected solution is almost always:

👉 the TreeNode version

Because:

Real trees are node-based
Array representation is usually input-only
Traversal problems assume pointer navigation

🧭 Mental model

You receiveUse

Array like [1,2,3,None,4]

Index math DFS

TreeNode object

Pointer DFS

So again:

Same DFS preorder idea Different data model TreeNode version is usually preferable in practice

Diego Portillo

Estudiante

Hace 7 meses•editado

Solution Exercise 1:

image = [
    [1,1,1],
    [1,1,0],
    [1,0,1]
]
expected_result = [
    [2,2,2],
    [2,2,0],
    [2,0,1]
]
expected_result_2 = [
    [0,0,0],
    [0,0,0]
]
def paint_image(image, sr, sc, new_color):
    start_color = image[sr][sc]
    if start_color == new_color:
        return image
    
    def dfs(i, j):
        # avoid out of limit error
        if not (0 <= i <len(image) and 0 <= j < len(image[i])):
            return  
        
        # avoid repainting
        if image[i][j] != start_color:
            return
        
        image[i][j] = new_color
        dfs(i+1,j)
        dfs(i-1,j)
        dfs(i,j+1)
        dfs(i,j-1)
        
    dfs(sr, sc)
    return image
print(paint_image(image, 0, 0, 2) == expected_result)
print(paint_image(expected_result_2,0,0,2) == expected_result_2)

Comparison with Teacher's solution:

🧩 1. Structural Difference

🔹 Your first one (paint_image)

Checks inside the DFS whether it should continue:

def dfs(i, j):    if not (0 <= i < len(image) and 0 <= j < len(image[i])):        return          if image[i][j] != start_color:        return    image[i][j] = new_color    dfs(i+1,j)    dfs(i-1,j)    dfs(i,j+1)    dfs(i,j-1)

So:

"Try to go everywhere, and stop if it’s invalid."

🔹 Your second one (colorearSector)

Checks before calling DFS:

for x, y in direcciones:    if valid AND same_color:        dfs(...)

So:

"Only go where I already know it's valid."

🧠 2. Conceptual Difference

Strategypaint_imagecolorearSector

DFS call

Calls first, validates later

Validates first, then calls

Invalid calls

Many

Fewer

Boundary check

Inside DFS

Outside DFS

Flow control

Defensive

Preventive

⚡ 3. Performance Difference

paint_image

This line:

dfs(i+1,j)dfs(i-1,j)dfs(i,j+1)dfs(i,j-1)

Always makes 4 recursive calls, even if:

the pixel is out of bounds
wrong color
already visited

Most of those calls immediately return.

So you get lots of:

useless function calls → more stack usage

colorearSector

Only calls DFS when:

0 <= x+i < len(imagen)ANDimagen[x+i][j+y] == colorActual

So it avoids:

unnecessary recursion
extra stack frames
wasted checks

🏁 4. Is one better?

✔️ colorearSector is:

more efficient
avoids unnecessary recursive calls
more scalable for big images

Because recursion is expensive in Python (stack frames are slow).

✔️ paint_image is:

easier to read
simpler logic
harder to mess up

Because all stopping logic lives in one place.

📌 Big-O?

Both are:

Time: O(N)
Space: O(N) (recursion stack)

But:

👉 paint_image has more constant overhead 👉 colorearSector is more optimal in practice

🧭 Rule of thumb

GoalUse

Clarity

paint_image

Efficiency

colorearSector

Interview

Either (but explain tradeoff)

Large grid

colorearSector

So:

Same algorithm Different control strategy Second one is usually better in real execution

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

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