Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes
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 indirecciones:if0<= 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.
# classTreeNode:# def __init__(self, val=0, izquierda=None, derecha=None):# self.val= val
# self.izquierda= izquierda
# self.derecha= derecha
classSolution: 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
returndfs(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).
def countBattleships(self,tablero:List[List[str]])-> int: def dfs(i,j):if0<= 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 =0for i inrange(len(tablero)):for j inrange(len(tablero[0])):if tablero[i][j]=='X':dfs(i,j) cantidad+=1return 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:iflen(mapa)==0:return0 def dfs(i,j):ifnot(0<=i<len(mapa) and 0<=j<len(mapa[0])):returnFalseif mapa[i][j]==1:returnTrue mapa[i][j]=1A=dfs(i+1,j)B=dfs(i-1,j)C=dfs(i,j+1)D=dfs(i,j-1)returnA and B and C and D cantidad =0for i inrange(len(mapa)):for j inrange(len(mapa[0])):if mapa[i][j]==0 and dfs(i,j): cantidad +=1return cantidad
input_1 =[["X",".","X"],["X",".","X"],["X",".","X"]]output_1 =2input_2 =[["."]]output_2 =0def count_ships(table): count =0for i inrange(len(table)):for j inrange(len(table[i])):if table[i][j]=='X': count +=1 stack =[(i, j)]whilestack: r, c = stack.pop()if0<= 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 insidedfs 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.
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 =1def count_closed_islands(grid): rows, cols =len(grid),len(grid[0]) count =0for i inrange(rows):for j inrange(cols):if grid[i][j]!=0: # 0=land(island)continue # Explorethisisland(connected 0s)withBFS stack =[(i, j)] touches_border =Falsewhilestack: 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 +=1return 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)returnA 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.
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) # ifthis is a leaf,return the value only
if left =='' and right =='':returnstr(array[index]) # if left doesn't exists we have to keep an empty pair of parentheses
if left =='':returnstr(array[index])+"()"+"("+ right +")" # if only left exists is not necessary to have the empty parentheses
if right =='':returnstr(array[index])+"("+ left +")" # if both exists put the parent node with each child in parenthesis
returnstr(array[index])+"("+ left +")("+ right +")" # go throught the input array starting from the index 0returndepth_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.
