В этом уроке ты
- Узнаешь что такое поиск в глубину (DFS) и где его применять.
- Решишь задачу с собеседования, используя поиск в глубину (DFS).
- Поймешь плюсы и минусы рекурсивной реализации DFS.
Поиск в глубину (DFS)
Поиск в глубину (или DFS, от английского Depth First Search) — это способ обхода графа или двумерной структуры (например, матрицы или сетки клеток).
Принцип работы достаточно простой: мы «идём» как можно глубже по одному направлению, а если дальше идти нельзя (закончились соседние непосещённые клетки или узлы), мы «возвращаемся назад» и пробуем другой путь.
В этом уроке мы рассмотрим задачу, где DFS помогает решать задачу раскраски «по номерам». Вместе с кодом ты увидишь, как алгоритм на практике обходит все клетки матрицы.
Задача с собеседования
Условие
Дана раскраска по номерам (двумерный массив colors). Нужно определить минимальное количество заливок, необходимых, чтобы «закрасить» всю картину.
Когда мы делаем «заливку» (например, в графическом редакторе), мы выбираем клетку, и одновременно «заливаются» все соседние клетки того же цвета. Соседними считаем клетки сверху, снизу, слева и справа.
Пример
Ввод: colors= [[1,1,1,1,1,1,1,1] ,[1,2,2,1,1,2,2,1] ,[1,2,1,2,2,1,2,1] ,[1,2,2,2,2,2,2,1] ,[1,1,1,1,1,1,1,1]] Вывод: 4
Ниже — код, который решает эту задачу. Прочитай его сначала сам, обрати внимание на главную функцию draw. Затем мы разберём детали.
using System;
using System.Collections.Generic;
public class Solution
{
// Проверяет, находятся ли индексы i и j в пределах матрицы
public static bool InBound(int i, int j, List<List<int>> colors)
{
return 0 <= i && i < colors.Count && 0 <= j && j < colors[0].Count;
}
// Вспомогательная функция для обхода графа
public static void Dfs(int i, int j, int needsColor, List<List<bool>> used, List<List<int>> colors)
{
// Если текущая клетка:
// - выходит за границы массива colors
// - или имеет цвет отличный от needsColor
// - или была уже закрашена ранее
// то возвращаемся к предыдущей клетке
if (!InBound(i, j, colors) || needsColor != colors[i][j] || used[i][j])
{
return;
}
// Закрашиваем текущую клетку
used[i][j] = true;
// Пробуем закрасить клетку СНИЗУ, СВЕРХУ, СПРАВА, СЛЕВА
Dfs(i + 1, j, needsColor, used, colors);
Dfs(i - 1, j, needsColor, used, colors);
Dfs(i, j + 1, needsColor, used, colors);
Dfs(i, j - 1, needsColor, used, colors);
}
// Основная функция, которая вернет результат
public static int Draw(List<List<int>> colors)
{
// Если used[i][j] = true, значит мы уже закрасили клетку colors[i][j]
var used = new List<List<bool>>();
for (int i = 0; i < colors.Count; i++)
{
used.Add(new List<bool>());
for (int j = 0; j < colors[0].Count; j++)
{
used[i].Add(false);
}
}
int result = 0;
// Пробуем сделать заливку из каждой клетки
for (int i = 0; i < colors.Count; i++)
{
for (int j = 0; j < colors[i].Count; j++)
{
// Если уже закрасили клетку, то пропускаем
if (!used[i][j])
{
Dfs(i, j, colors[i][j], used, colors);
result++;
}
}
}
return result;
}
}#include <vector>
#include <iostream>
using namespace std;
// Проверяет, находятся ли индексы i и j в пределах матрицы
bool inBound(int i, int j, const vector<vector<int>>& colors) {
return 0 <= i && i < colors.size() && 0 <= j && j < colors[0].size();
}
// Вспомогательная функция для обхода графа
void dfs(int i, int j, int needsColor, vector<vector<bool>>& used, const vector<vector<int>>& colors) {
// Если текущая клетка:
// - выходит за границы массива colors
// - или имеет цвет отличный от needsColor
// - или была уже закрашена ранее
// то возвращаемся к предыдущей клетке
if (!inBound(i, j, colors) || needsColor != colors[i][j] || used[i][j]) {
return;
}
// Закрашиваем текущую клетку
used[i][j] = true;
// Пробуем закрасить клетку СНИЗУ, СВЕРХУ, СПРАВА, СЛЕВА
dfs(i + 1, j, needsColor, used, colors);
dfs(i - 1, j, needsColor, used, colors);
dfs(i, j + 1, needsColor, used, colors);
dfs(i, j - 1, needsColor, used, colors);
}
// Основная функция, которая вернет результат
int draw(const vector<vector<int>>& colors) {
// Если used[i][j] = true, значит мы уже закрасили клетку colors[i][j]
vector<vector<bool>> used(colors.size(), vector<bool>(colors[0].size(), false));
int result = 0;
// Пробуем сделать заливку из каждой клетки
for (int i = 0; i < colors.size(); i++) {
for (int j = 0; j < colors[i].size(); j++) {
// Если уже закрасили клетку, то пропускаем
if (!used[i][j]) {
dfs(i, j, colors[i][j], used, colors);
result++;
}
}
}
return result;
}package main
// Проверяет, находятся ли индексы i и j в пределах матрицы
func inBound(i, j int, colors [][]int) bool {
return 0 <= i && i < len(colors) && 0 <= j && j < len(colors[0])
}
// Вспомогательная функция для обхода графа
func dfs(i, j, needsColor int, used [][]bool, colors [][]int) {
// Если текущая клетка:
// - выходит за границы массива colors
// - или имеет цвет отличный от needsColor
// - или была уже закрашена ранее
// то возвращаемся к предыдущей клетке
if !inBound(i, j, colors) || needsColor != colors[i][j] || used[i][j] {
return
}
// Закрашиваем текущую клетку
used[i][j] = true
// Пробуем закрасить клетку СНИЗУ, СВЕРХУ, СПРАВА, СЛЕВА
dfs(i+1, j, needsColor, used, colors)
dfs(i-1, j, needsColor, used, colors)
dfs(i, j+1, needsColor, used, colors)
dfs(i, j-1, needsColor, used, colors)
}
// Основная функция, которая вернет результат
func draw(colors [][]int) int {
// Если used[i][j] = true, значит мы уже закрасили клетку colors[i][j]
used := make([][]bool, len(colors))
for i := range used {
used[i] = make([]bool, len(colors[0]))
}
result := 0
// Пробуем сделать заливку из каждой клетки
for i := 0; i < len(colors); i++ {
for j := 0; j < len(colors[i]); j++ {
// Если уже закрасили клетку, то пропускаем
if !used[i][j] {
dfs(i, j, colors[i][j], used, colors)
result++
}
}
}
return result
}import java.util.*;
public class Solution {
// Проверяет, находятся ли индексы i и j в пределах матрицы
public static boolean inBound(int i, int j, List<List<Integer>> colors) {
return 0 <= i && i < colors.size() && 0 <= j && j < colors.get(0).size();
}
// Вспомогательная функция для обхода графа
public static void dfs(int i, int j, int needsColor, List<List<Boolean>> used, List<List<Integer>> colors) {
// Если текущая клетка:
// - выходит за границы массива colors
// - или имеет цвет отличный от needsColor
// - или была уже закрашена ранее
// то возвращаемся к предыдущей клетке
if (!inBound(i, j, colors) || needsColor != colors.get(i).get(j) || used.get(i).get(j)) {
return;
}
// Закрашиваем текущую клетку
used.get(i).set(j, true);
// Пробуем закрасить клетку СНИЗУ, СВЕРХУ, СПРАВА, СЛЕВА
dfs(i + 1, j, needsColor, used, colors);
dfs(i - 1, j, needsColor, used, colors);
dfs(i, j + 1, needsColor, used, colors);
dfs(i, j - 1, needsColor, used, colors);
}
// Основная функция, которая вернет результат
public static int draw(List<List<Integer>> colors) {
// Если used[i][j] = true, значит мы уже закрасили клетку colors[i][j]
List<List<Boolean>> used = new ArrayList<>();
for (List<Integer> row : colors) {
List<Boolean> usedRow = new ArrayList<>();
for (int k = 0; k < row.size(); k++) {
usedRow.add(false);
}
used.add(usedRow);
}
int result = 0;
// Пробуем сделать заливку из каждой клетки
for (int i = 0; i < colors.size(); i++) {
for (int j = 0; j < colors.get(i).size(); j++) {
// Если уже закрасили клетку, то пропускаем
if (!used.get(i).get(j)) {
dfs(i, j, colors.get(i).get(j), used, colors);
result++;
}
}
}
return result;
}
}# in_bound возвращает true, если обе координаты i и j
# не выходят за границы массива colors
def in_bound(i: int, j: int, colors: List[List[int]]) -> bool:
return 0 <= i < len(colors) and 0 <= j < len(colors[0])
# Вспомогательная функция для обхода графа
def dfs(i: int, j: int, needs_color: int, used: List[List[bool]], colors: List[List[int]]) -> None:
# Если текущая клетка:
# - выходит за границы массива colors
# - или имеет цвет отличный от needs_color
# - или была уже закрашена ранее
# то возвращаемся к предыдущей клетке
if not in_bound(i, j, colors) or needs_color != colors[i][j] or used[i][j]:
return
# Закрашиваем текущую клетку
used[i][j] = True
# Пробуем закрасить клетку СНИЗУ, если ее значение такое же, как у текущей
dfs(i + 1, j, needs_color, used, colors)
# Пробуем закрасить клетку СВЕРХУ, если ее значение такое же, как у текущей
dfs(i - 1, j, needs_color, used, colors)
# Пробуем закрасить клетку СПРАВА, если ее значение такое же, как у текущей
dfs(i, j + 1, needs_color, used, colors)
# Пробуем закрасить клетку СЛЕВА, если ее значение такое же, как у текущей
dfs(i, j - 1, needs_color, used, colors)
# Основная функция, которая вернет результат
def draw(colors: List[List[int]]) -> int:
# Если used[i][j] = true, значит мы уже закрасили клетку colors[i][j]
used = [[False for _ in range(len(el))] for el in colors]
result = 0
# Пробуем сделать заливку из каждой клетки
for i in range(len(colors)):
for j in range(len(colors[i])):
# Если уже закрасили клетку, то пропускаем
if not used[i][j]:
dfs(i, j, colors[i][j], used, colors)
result += 1
return result// Проверяет, находятся ли индексы i и j в пределах матрицы
function inBound(i, j, colors) {
return 0 <= i && i < colors.length && 0 <= j && j < colors[0].length;
}
// Вспомогательная функция для обхода графа
function dfs(i, j, needsColor, used, colors) {
// Если текущая клетка:
// - выходит за границы массива colors
// - или имеет цвет отличный от needsColor
// - или была уже закрашена ранее
// то возвращаемся к предыдущей клетке
if (!inBound(i, j, colors) || needsColor !== colors[i][j] || used[i][j]) {
return;
}
// Закрашиваем текущую клетку
used[i][j] = true;
// Пробуем закрасить клетку СНИЗУ, СВЕРХУ, СПРАВА, СЛЕВА
dfs(i + 1, j, needsColor, used, colors);
dfs(i - 1, j, needsColor, used, colors);
dfs(i, j + 1, needsColor, used, colors);
dfs(i, j - 1, needsColor, used, colors);
}
// Основная функция, которая вернет результат
function draw(colors) {
// Если used[i][j] = true, значит мы уже закрасили клетку colors[i][j]
const used = colors.map(row => row.map(() => false));
let result = 0;
// Пробуем сделать заливку из каждой клетки
for (let i = 0; i < colors.length; i++) {
for (let j = 0; j < colors[i].length; j++) {
// Если уже закрасили клетку, то пропускаем
if (!used[i][j]) {
dfs(i, j, colors[i][j], used, colors);
result++;
}
}
}
return result;
}- В
drawсоздаём двумерный массивused, где все значения изначальноfalse. - Начинаем обходить каждую клетку:
- если видим, что клетка не была закрашена, запускаем на неё DFS.
- Внутри DFS мы «заливаем» (помечаем
used[i][j] = true) все соседние клетки такого же цвета, в глубину — пока не дойдём до границы или до клетки другого цвета. - Когда DFS завершает обход, мы увеличиваем
result— это значит, что мы начали новую заливку.
3. В итоге в result хранится количество заливок, необходимое для покраски всей раскраски.
Упрощаем решение
Ниже — чуть более компактный вариант, где мы используем цикл для обхода соседей, а не четыре отдельных вызова.
using System;
using System.Collections.Generic;
public class Solution
{
public static bool InBound(int i, int j, List<List<int>> colors)
{
return 0 <= i && i < colors.Count && 0 <= j && j < colors[0].Count;
}
public static void Dfs(int i, int j, int needsColor, bool[][] used, List<List<int>> colors)
{
if (!InBound(i, j, colors) || needsColor != colors[i][j] || used[i][j])
{
return;
}
used[i][j] = true;
// Используем цикл вместо нескольких вызовов функции
var nextSteps = new (int, int)[] { (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j) };
foreach (var nextStep in nextSteps)
{
Dfs(nextStep.Item1, nextStep.Item2, needsColor, used, colors);
}
}
public static int Draw(List<List<int>> colors)
{
var used = new bool[colors.Count][];
for (int i = 0; i < used.Length; i++)
{
used[i] = new bool[colors[0].Count];
}
int result = 0;
for (int i = 0; i < colors.Count; i++)
{
for (int j = 0; j < colors[i].Count; j++)
{
if (!used[i][j])
{
Dfs(i, j, colors[i][j], used, colors);
result++;
}
}
}
return result;
}
}#include <vector>
using namespace std;
bool in_bound(int i, int j, const vector<vector<int>>& colors) {
return 0 <= i && i < colors.size() && 0 <= j && j < colors[0].size();
}
void dfs(int i, int j, int needs_color, vector<vector<bool>>& used, const vector<vector<int>>& colors) {
if (!in_bound(i, j, colors) || needs_color != colors[i][j] || used[i][j]) {
return;
}
used[i][j] = true;
// Используем цикл вместо нескольких вызовов функции
vector<vector<int>> next_steps = { {i, j + 1}, {i, j - 1}, {i + 1, j}, {i - 1, j} };
for (const auto& next_step : next_steps) {
dfs(next_step[0], next_step[1], needs_color, used, colors);
}
}
int draw(const vector<vector<int>>& colors) {
vector<vector<bool>> used(colors.size(), vector<bool>(colors[0].size(), false));
int result = 0;
for (int i = 0; i < colors.size(); ++i) {
for (int j = 0; j < colors[i].size(); ++j) {
if (!used[i][j]) {
dfs(i, j, colors[i][j], used, colors);
result++;
}
}
}
return result;
}package main
func inBound(i, j int, colors [][]int) bool {
return 0 <= i && i < len(colors) && 0 <= j && j < len(colors[0])
}
func dfs(i, j, needsColor int, used [][]bool, colors [][]int) {
if !inBound(i, j, colors) || needsColor != colors[i][j] || used[i][j] {
return
}
used[i][j] = true
// Используем цикл вместо нескольких вызовов функции
nextSteps := [][]int{{i, j + 1}, {i, j - 1}, {i + 1, j}, {i - 1, j}}
for _, nextStep := range nextSteps {
dfs(nextStep[0], nextStep[1], needsColor, used, colors)
}
}
func draw(colors [][]int) int {
used := make([][]bool, len(colors))
for i := range used {
used[i] = make([]bool, len(colors[0]))
}
result := 0
for i := 0; i < len(colors); i++ {
for j := 0; j < len(colors[i]); j++ {
if !used[i][j] {
dfs(i, j, colors[i][j], used, colors)
result++
}
}
}
return result
}import java.util.List;
public class Solution {
public static boolean inBound(int i, int j, List<List<Integer>> colors) {
return 0 <= i && i < colors.size() && 0 <= j && j < colors.get(0).size();
}
public static void dfs(int i, int j, int needsColor, boolean[][] used, List<List<Integer>> colors) {
if (!inBound(i, j, colors) || needsColor != colors.get(i).get(j) || used[i][j]) {
return;
}
used[i][j] = true;
// Используем цикл вместо нескольких вызовов функции
int[][] nextSteps = { {i, j + 1}, {i, j - 1}, {i + 1, j}, {i - 1, j} };
for (int[] nextStep : nextSteps) {
dfs(nextStep[0], nextStep[1], needsColor, used, colors);
}
}
public static int draw(List<List<Integer>> colors) {
boolean[][] used = new boolean[colors.size()][colors.get(0).size()];
int result = 0;
for (int i = 0; i < colors.size(); i++) {
for (int j = 0; j < colors.get(i).size(); j++) {
if (!used[i][j]) {
dfs(i, j, colors.get(i).get(j), used, colors);
result++;
}
}
}
return result;
}
}def in_bound(i: int, j: int, colors: List[List[int]]) -> bool:
return 0 <= i < len(colors) and 0 <= j < len(colors[0])
def dfs(i: int, j: int, needs_color: int, used: List[List[bool]], colors: List[List[int]]) -> None:
if not in_bound(i, j, colors) or needs_color != colors[i][j] or used[i][j]:
return
used[i][j] = True
# Используем цикл вместо нескольких вызовов функции
next_steps = [[i, j+1], [i, j-1], [i+1, j], [i-1, j]]
for next_step in next_steps:
dfs(next_step[0], next_step[1], needs_color, used, colors)
def draw(colors: List[List[int]]) -> int:
used = [[False for _ in range(len(el))] for el in colors]
result = 0
for i in range(len(colors)):
for j in range(len(colors[i])):
if not used[i][j]:
dfs(i, j, colors[i][j], used, colors)
result += 1
return resultfunction inBound(i, j, colors) {
return 0 <= i && i < colors.length && 0 <= j && j < colors[0].length;
}
function dfs(i, j, needsColor, used, colors) {
if (!inBound(i, j, colors) || needsColor !== colors[i][j] || used[i][j]) {
return;
}
used[i][j] = true;
// Используем цикл вместо нескольких вызовов функции
const nextSteps = [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]];
for (const nextStep of nextSteps) {
dfs(nextStep[0], nextStep[1], needsColor, used, colors);
}
}
function draw(colors) {
const used = Array.from({ length: colors.length }, () => Array(colors[0].length).fill(false));
let result = 0;
for (let i = 0; i < colors.length; i++) {
for (let j = 0; j < colors[i].length; j++) {
if (!used[i][j]) {
dfs(i, j, colors[i][j], used, colors);
result++;
}
}
}
return result;
}Суть алгоритма не меняется: мы так же рекурсивно обходим все соседние клетки такого же цвета.
Паттерн DFS
При решении похожих задач часто можно использовать такой «каркас» кода:
using System.Collections.Generic;
public class Solution
{
// Проверка, можно ли зайти в клетку
public static bool InBound(int i, int j, List<List<int>> matrix)
{
return 0 <= i && i < matrix.Count && 0 <= j && j < matrix[0].Count;
}
// Могут быть и другие аргументы
public static void Dfs(int i, int j, bool[][] used /* другие аргументы */)
{
// Проверяем, можно ли зайти в клетку
if (!InBound(i, j, matrix) || used[i][j])
{
return;
}
// Помечаем, что посетили клетку
used[i][j] = true;
// Рекурсивно идём в соседние клетки
// ...
}
}#include <vector>
using namespace std;
// Проверка, можно ли зайти в клетку
bool in_bound(int i, int j, const vector<vector<int>>& matrix) {
return 0 <= i && i < matrix.size() && 0 <= j && j < matrix[0].size();
}
// Могут быть и другие аргументы
void dfs(int i, int j, vector<vector<bool>>& used /* другие аргументы */) {
// Проверяем, можно ли зайти в клетку
if (!in_bound(i, j, matrix) || used[i][j]) {
return;
}
// Помечаем, что посетили клетку
used[i][j] = true;
// Рекурсивно идём в соседние клетки
// ...
}package main
func inBound(i, j int, matrix [][]int) bool {
return 0 <= i && i < len(matrix) && 0 <= j && j < len(matrix[0])
}
// Могут быть и другие аргументы
func dfs(i, j int, used [][]bool /* другие аргументы */) {
// Проверяем, можно ли зайти в клетку
if !inBound(i, j, matrix) || used[i][j] {
return
}
// Помечаем, что посетили клетку
used[i][j] = true
// Рекурсивно идём в соседние клетки
// ...
}import java.util.List;
public class Solution {
// Проверка, можно ли зайти в клетку
public static boolean inBound(int i, int j, List<List<Integer>> matrix) {
return 0 <= i && i < matrix.size() && 0 <= j && j < matrix.get(0).size();
}
// Могут быть и другие аргументы
public static void dfs(int i, int j, boolean[][] used /* другие аргументы */) {
// Проверяем, можно ли зайти в клетку
if (!inBound(i, j, matrix) || used[i][j]) {
return;
}
// Помечаем, что посетили клетку
used[i][j] = true;
// Рекурсивно идём в соседние клетки
// ...
}
}def in_bound(i: int, j: int, matrix: List[List[int]]) -> bool:
return 0 <= i < len(matrix) and 0 <= j < len(matrix[0])
# Могут быть и другие аргументы
def dfs(i: int, j: int, used: List[List[bool]], ...):
# Проверяем, можно ли зайти в клетку
if not in_bound(i, j, matrix) or used[i][j]:
return
# Помечаем, что посетили клетку
used[i][j] = True
# Рекурсивно идём в соседние клетки
...function inBound(i, j, matrix) {
return 0 <= i && i < matrix.length && 0 <= j && j < matrix[0].length;
}
// Могут быть и другие аргументы
function dfs(i, j, used /* другие аргументы */) {
// Проверяем, можно ли зайти в клетку
if (!inBound(i, j, matrix) || used[i][j]) {
return;
}
// Помечаем, что посетили клетку
used[i][j] = true;
// Рекурсивно идём в соседние клетки
// ...
}Большинство задач по типу «Обойти всю область» (в двумерных массивах) сводятся к похожему подходу:
- Проверить, не вышли ли за границы (
inBound). - Проверить, не посещали ли уже эту клетку (массив
used). - Если всё хорошо — запомнить, что мы “обработали” данную клетку и рекурсивно пойти к её соседям.
Оценка сложности
- Временная сложность:
O(n * m), гдеnm - Пространственная сложность:
O(n * m)для стека рекурсии.
Плюсы рекурсивного DFS
- Простота реализации: легко запомнить и писать на собеседованиях.
- Компактность кода: меньше строк по сравнению с итеративным решением.
Минусы рекурсивного DFS
- Ограничения по глубине рекурсии: при очень больших матрицах можно получить ошибку Stack Overflow.
- Работает медленнее итеративных решений из-за затрат на вызов функций.
- Без дополнительных настроек (увеличения стековой области памяти) невозможно обрабатывать большие объёмы данных.
Неочевидные выводы
На практике рекурсивный DFS достаточно быстр и удобен. На собеседованиях рекурсивную версию обычно и ждут, так что умение её быстро написать — хорошее преимущество.
Если ты хочешь удивить интервьюера, можешь использовать итеративное решение, которое мы разберём в следующих модулях. А пока попрактикуйся в написании рекурсивного DFS, чтобы у тебя всегда было решение, которое ты можешь без ошибок написать с первого раза.
Что дальше
Теперь попробуй решить эту задачку самостоятельно, чтобы закрепить полученные навыки!