Bài 12.6 - Bài toán đếm đảo bằng Python

Bài toán đếm số đảo (Number of Islands) là một trong những bài kinh điển giúp bạn làm quen với tư duy quy hoạch theo vùng bằng DFS hoặc BFS trong ma trận.

Đề bài

Cho một ma trận nhị phân grid với các giá trị '1' (đất) và '0' (nước), hãy đếm xem có bao nhiêu đảo trong ma trận.

Một đảo được tạo thành từ các ô '1' liền kề theo chiều dọc hoặc ngang (không chéo).

Ví dụ minh hoạ

Ví dụ 1:
grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

Kết quả mong đợi: 3

Có 3 đảo riêng biệt trong lưới: một cụm ở góc trái trên, một ở giữa, và một ở góc phải dưới.

Cách giải bằng DFS (Đệ quy)

Bước tiếp cận:
  1. Duyệt từng ô trong ma trận.
  2. Nếu gặp '1', kích hoạt DFS để “nhấn chìm” cả đảo (đánh dấu đã thăm).
  3. Mỗi lần như vậy, tăng biến đếm đảo lên 1.
Cài đặt bằng Python
def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # Đánh dấu đã thăm
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1

    return count

Ví dụ minh hoạ 2

grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

print("Số đảo:", num_islands(grid))  # Output: 3

Hàm DFS sẽ lặp qua từng cụm '1' và “chìm” toàn bộ cụm đó, đảm bảo không đếm lại.

Cách khác: BFS (Hàng đợi)

from collections import deque

def num_islands_bfs(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def bfs(r, c):
        queue = deque()
        queue.append((r, c))
        grid[r][c] = '0'

        while queue:
            row, col = queue.popleft()
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    queue.append((nr, nc))
                    grid[nr][nc] = '0'

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                bfs(r, c)
                count += 1

    return count

Kết quả với cùng dữ liệu:

print("Số đảo (BFS):", num_islands_bfs([
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]))  # Output: 3

BFS hoạt động tương tự DFS, nhưng dùng hàng đợi để duyệt lần lượt theo chiều rộng.

Độ phức tạp

Phép tính Giá trị
Thời gian O(m × n)
Bộ nhớ O(m × n)

Trong đó:

  • m, n là số hàng, cột của ma trận.

Gợi ý mở rộng

  • Tính diện tích đảo lớn nhất (max_area_of_island)
  • Đếm số cụm '0' thay vì '1'
  • Tìm số bước ít nhất để kết nối 2 đảo (bài Leetcode 934)

Tổng kết

  • Bài toán đếm đảo là một ứng dụng kinh điển của DFS/BFS trên ma trận.
  • Học được cách xử lý ma trận, tìm vùng liên thông, đánh dấu đỉnh đã thăm.
  • Là nền tảng cho nhiều bài toán giải mê cung, cụm liên kết, phân vùng dữ liệu...

Khóa học liên quan

Khoá học lập trình Python Giảm giá!
Ưu đãi có hạn
Khoá học lập trình Python
4.8 120 giờ
3300000 4500000
Học Ngay

Comments

There are no comments at the moment.