Number of Islands: 0 ve 1'lerden oluşan bir grid'de kaç ada olduğunu bulun.

Grid'i bir graf olarak düşünürüz: her 1 hücresi bir düğüm, yatay/dikey komşular kenardır. Her ziyaret edilmemiş 1 hücresinden bir DFS/BFS başlatıp bağlı tüm hücreleri işaretleriz; kaç kez arama başlattıysak o kadar ada vardır.

from collections import deque

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def bfs(r, c):
        q = deque([(r, c)])
        grid[r][c] = "0"                 # ziyaret edildi
        while q:
            x, y = q.popleft()
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1":
                    grid[nx][ny] = "0"
                    q.append((nx, ny))

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

grid = [list("11000"), list("11000"), list("00100"), list("00011")]
print(num_islands(grid))  # 3

Karmaşıklık

• Zaman: O(R x C), her hücre en fazla bir kez işlenir.
• Bellek: BFS kuyruğu en kötü O(min(R, C)); özyinelemeli DFS ise en kötü O(R x C) stack derinliği.

Tartışılacak noktalar

• Girdiyi değiştirmek kabul edilebilir mi? Değilse ayrı bir visited kümesi kullanın.
• Büyük grid'de özyinelemeli DFS Python'da RecursionError verebilir; BFS veya açık stack daha güvenlidir.
• Union-Find ile de çözülebilir; grid sürekli güncelleniyorsa (Number of Islands II) Union-Find tercih edilir.