1. Khái niệm cốt lõi về tìm kiếm

Trong lập trình thuật toán, tìm kiếm (Search) là chiến lược khám phá hệ thống một không gian các lời giải khả thi để tìm ra một hoặc toàn bộ các cấu hình thỏa mãn điều kiện cho trước. Đây là nền tảng của các bài toán tối ưu hóa và tổ hợp khi không có công thức giải trực tiếp.

Tìm kiếm theo chiều sâu (Depth-First Search - DFS): Hoạt động theo nguyên tắc thám hiểm một nhánh xa nhất có thể trước khi quay lui (backtracking). DFS thường tận dụng cấu trúc dữ liệu Ngăn xếp (Stack) hoặc cơ chế đệ quy để ghi nhớ lộ trình.

Tìm kiếm theo chiều rộng (Breadth-First Search - BFS): Lan tỏa theo từng lớp (layer-by-layer). Từ điểm xuất phát, thuật toán thăm tất cả các nút lân cận trước khi tiến xa hơn. BFS sử dụng Hàng đợi (Queue) để đảm bảo thứ tự "vào trước ra trước", giúp tìm đường đi ngắn nhất trong đồ thị không trọng số.

2. Khi nào nên áp dụng thuật toán tìm kiếm?

• Mô hình hóa trạng thái: Bài toán có thể định nghĩa rõ ràng "Trạng thái" (ví dụ: tọa độ trong mê cung) và "Phép chuyển trạng thái" (ví dụ: di chuyển sang ô cạnh bên).
• Yêu cầu liệt kê: Khi cần tìm tất cả các tổ hợp (ví dụ: bài toán N-Hậu, hoán vị) thay vì chỉ một giá trị tối ưu đơn thuần.
• Không gian trạng thái hữu hạn: Do độ phức tạp thường là hàm mũ (O(2^N) hoặc O(N!)), tìm kiếm chỉ khả thi khi quy mô dữ liệu nhỏ hoặc có thể thực hiện kỹ thuật "cắt tỉa" (pruning).

Lựa chọn chiến lược:

• Dùng BFS khi: Cần tìm đường đi ngắn nhất hoặc số bước ít nhất; cây tìm kiếm rộng nhưng không quá sâu.
• Dùng DFS khi: Cần khám phá toàn bộ các phương án khả thi; không gian bộ nhớ hạn chế (DFS tốn ít bộ nhớ hơn BFS vì không phải lưu toàn bộ các nút ở cùng một cấp độ).

3. Các khung mã nguồn (Template) cơ bản

Khung DFS sử dụng Đệ quy:

void performDFS(Node* curr, unordered_set<Node*>& visited) {
    if (!curr || visited.count(curr)) return;
    
    // Xử lý logic tại nút hiện tại
    process(curr);
    visited.insert(curr);

    for (Node* neighbor : curr->adjacents) {
        performDFS(neighbor, visited);
    }
}

Khung BFS sử dụng Hàng đợi:

void performBFS(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        int nodesAtLevel = q.size();
        for (int i = 0; i < nodesAtLevel; ++i) {
            Node* node = q.front();
            q.pop();
            
            // Xử lý node
            process(node);
            
            for (Node* next : node->neighbors) {
                if (isValid(next)) q.push(next);
            }
        }
    }
}

4. Các bài toán điển hình

Bài toán 1: Đếm số lượng đảo (Số vùng liên thông)

Cho một ma trận 2D gồm '1' (đất) và '0' (nước), hãy đếm số lượng hòn đảo được bao quanh bởi nước.

class IslandExplorer {
public:
    int totalIslands(vector<vector<char>>& ocean) {
        if (ocean.empty()) return 0;
        int m = ocean.size(), n = ocean[0].size();
        int count = 0;

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (ocean[r][c] == '1') {
                    count++;
                    sinkIslandDFS(ocean, r, c);
                }
            }
        }
        return count;
    }

private:
    void sinkIslandDFS(vector<vector<char>>& grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] == '0') {
            return;
        }
        grid[r][c] = '0'; // Đánh dấu đã thăm bằng cách chuyển về '0'
        sinkIslandDFS(grid, r + 1, c);
        sinkIslandDFS(grid, r - 1, c);
        sinkIslandDFS(grid, r, c + 1);
        sinkIslandDFS(grid, r, c - 1);
    }
};

Bài toán 2: Xếp diêm thành hình vuông

Sử dụng tất cả các que diêm cho trước để tạo thành một hình vuông mà không bẻ gãy bất kỳ que diêm nào.

class MatchstickSquare {
public:
    bool canFold(vector<int>& sticks) {
        long long totalLen = 0;
        for (int s : sticks) totalLen += s;
        if (sticks.size() < 4 || totalLen % 4 != 0) return false;

        sort(sticks.rbegin(), sticks.rend()); // Tối ưu: Thử que dài trước
        vector<int> sides(4, 0);
        return backtrack(sticks, sides, 0, totalLen / 4);
    }

private:
    bool backtrack(vector<int>& sticks, vector<int>& sides, int idx, int target) {
        if (idx == sticks.size()) {
            return sides[0] == target && sides[1] == target && sides[2] == target;
        }

        for (int i = 0; i < 4; ++i) {
            if (sides[i] + sticks[idx] > target) continue;
            
            // Tối ưu: Nếu cạnh hiện tại giống cạnh trước đó đã thử, bỏ qua
            int j = i;
            while (--j >= 0) if (sides[i] == sides[j]) break;
            if (j != -1) continue;

            sides[i] += sticks[idx];
            if (backtrack(sticks, sides, idx + 1, target)) return true;
            sides[i] -= sticks[idx];
        }
        return false;
    }
};

Bài toán 3: Tiếp nhận nước mưa II (3D)

Tính thể tích nước có thể giữ lại trên một bản đồ độ cao 2D bằng cách sử dụng hàng đợi ưu tiên (Min-Heap) để tìm điểm biên thấp nhất.

struct Cell {
    int r, c, h;
    bool operator>(const Cell& other) const { return h > other.h; }
};

int trapWater3D(vector<vector<int>>& terrain) {
    int rows = terrain.size();
    if (rows == 0) return 0;
    int cols = terrain[0].size();
    priority_queue<Cell, vector<Cell>, greater<Cell>> minHeap;
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));

    // Đưa tất cả các ô biên vào heap
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                minHeap.push({i, j, terrain[i][j]});
                visited[i][j] = true;
            }
        }
    }

    int waterVolume = 0;
    int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};

    while (!minHeap.empty()) {
        Cell curr = minHeap.top();
        minHeap.pop();

        for (int i = 0; i < 4; ++i) {
            int nr = curr.r + dr[i], nc = curr.c + dc[i];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                visited[nr][nc] = true;
                waterVolume += max(0, curr.h - terrain[nr][nc]);
                minHeap.push({nr, nc, max(terrain[nr][nc], curr.h)});
            }
        }
    }
    return waterVolume;
}