LeetCode #200 Number of Islands: Flood Fill, BFS หรือ Union-Find เลือกตามข้อจำกัด

โจทย์ให้กริดตัวอักษร 1 เป็นบกและ 0 เป็นน้ำ แล้วนับกลุ่มบกที่เชื่อมกันสี่ทิศครับ ทุกครั้งที่พบ 1 ซึ่งยังไม่เคยเยี่ยม เราพบเกาะใหม่ จากนั้นทำ flood fill ให้ครบเกาะเพื่อไม่ให้นับซ้ำ

วิธีที่ 1: DFS และจมเกาะในกริด — ค่าเริ่มต้นที่แนะนำเมื่อแก้ input ได้

เปลี่ยน 1 ที่เยี่ยมแล้วเป็น 0 จึงไม่ต้องมี visited set เวลา O(rows×cols), พื้นที่ worst-case O(rows×cols) จาก recursion stack ในเกาะใหญ่ Python อาจชน recursion limit จึงเหมาะกับกริดไม่ลึกมากหรือควรเปลี่ยนเป็น stack explicit

วิธีที่ 2: BFS พร้อม visited set

ใช้ queue ขยายทีละชั้นและเก็บพิกัดที่เห็น เวลา O(rows×cols), พื้นที่ O(rows×cols) ไม่เสี่ยง call stack และไม่แก้ input เหมาะเมื่อ caller ต้องใช้กริดต่อ

วิธีที่ 3: Union-Find

สร้าง parent ให้เซลล์บก แล้ว union กับเพื่อนขวา/ล่าง เวลาใกล้ O(rows×cols·α(n)), พื้นที่ O(rows×cols) โค้ดยาวกว่าสำหรับกริดคงที่ แต่เหมาะเมื่อมีการเพิ่มบกเป็นลำดับและต้องตอบจำนวน component หลายครั้ง

import unittest
from collections import deque


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

    def sink(r, c):
        if r < 0 or r == rows or c < 0 or c == cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)

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


def islands_bfs(grid):
    if not grid:
        return 0
    rows, cols, seen, count = len(grid), len(grid[0]), set(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or (r, c) in seen:
                continue
            count += 1
            queue = deque([(r, c)]); seen.add((r, c))
            while queue:
                x, y = queue.popleft()
                for nx, ny in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1" and (nx, ny) not in seen:
                        seen.add((nx, ny)); queue.append((nx, ny))
    return count


class NumberOfIslandsTests(unittest.TestCase):
    def test_examples_and_edges(self):
        cases = [([], 0), ([["0"]], 0), ([["1"]], 1),
                 ([list("11000"), list("11000"), list("00100"), list("00011")], 3)]
        for grid, expected in cases:
            self.assertEqual(islands_dfs([row[:] for row in grid]), expected)
            self.assertEqual(islands_bfs([row[:] for row in grid]), expected)


if __name__ == "__main__":
    unittest.main()

เลือกตามสถานการณ์

เงื่อนไข	DFS จมกริด	BFS + visited	Union-Find
input ใหญ่/เกาะลึก	recursion เสี่ยง	queue ควบคุมได้	ดีแต่โครงสร้างใหญ่
memory จำกัด	ดีถ้าแก้กริดได้	visited O(RC)	parent O(RC)
readability	สั้นที่สุด	ชัดและไม่พึ่ง recursion	ซับซ้อนกว่า
sorted/streaming rows	การ sort ไม่ช่วย; ต้องมีเพื่อนบ้าน	ปกติต้องเก็บกริด/visited	ปรับเป็น streaming สองแถวได้
อนุญาตแก้ input	ต้องอนุญาตในแบบนี้	ไม่แก้	ไม่จำเป็น

best default ตามโจทย์คือ DFS จมกริดถ้า mutation อนุญาตและขนาดไม่ชน recursion; สำหรับ Python input ใหญ่มากใช้ BFS หรือ iterative DFS

Edge cases

กริดว่าง, น้ำทั้งหมด, บกช่องเดียว, เกาะแตะขอบ และแนวทแยงต้องไม่นับว่าเชื่อม ตรวจด้วยว่าทุกแถวยาวเท่ากันก่อนใช้กับข้อมูลนอก LeetCode เพราะโจทย์รับประกัน rectangular grid แต่ระบบจริงอาจไม่ให้

Recap

• พบ 1 ใหม่หนึ่งครั้งเท่ากับเกาะใหม่หนึ่งเกาะ
• flood fill สี่ทิศเพื่อ mark ทั้ง component
• mutation ลด visited memory แต่เปลี่ยน input
• Union-Find คุ้มเมื่อมี update/query ซ้ำ ไม่ใช่คำตอบสั้นสุดสำหรับ snapshot เดียว