Number of Islands

O Number of Islands é um problema clássico de busca em grafos / matrizes, muito usado para ensinar DFS, BFS e Union-Find.

---

Enunciado (forma comum)

Dada uma matriz 2D grid composta por '1' (terra) e '0' (água), conte quantas ilhas existem.

• Uma ilha é formada por células de terra conectadas horizontal ou verticalmente.
• As bordas do grid são cercadas por água.

Exemplo

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Resultado: 3

---

Ideia central

O problema se reduz a:

Contar quantos componentes conexos de '1' existem no grid.

Cada vez que encontramos um '1' ainda não visitado, descobrimos uma nova ilha e visitamos toda a sua extensão.

---

Abordagem 1 - DFS (mais didática)

Ideia

• Percorra todas as células

• Ao encontrar '1':

  • Incrementa o contador de ilhas
  • Execute DFS para “afundar” toda a ilha (marcar como visitada)

Implementação (Python)

def numIslands(grid):
    if not grid:
        return 0
 
    rows, cols = len(grid), len(grid[0])
    islands = 0
 
    def dfs(r, c):
        if (
            r < 0 or r >= rows or
            c < 0 or c >= cols or
            grid[r][c] == "0"
        ):
            return
 
        grid[r][c] = "0"  # marca como visitado
 
        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":
                islands += 1
                dfs(r, c)
 
    return islands

Complexidade

• Tempo: O(m · n)
• Espaço: O(m · n) no pior caso (stack de recursão)

---

Abordagem 2 - BFS

Ideia

Igual ao DFS, mas usando fila.

Implementação

from collections import deque
 
def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    islands = 0
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                queue = deque([(r, c)])
                grid[r][c] = "0"
 
                while queue:
                    x, y = queue.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"
                            queue.append((nx, ny))
 
    return islands

Complexidade

• Tempo: O(m · n)
• Espaço: O(min(m, n)) (fila no pior caso)

---

Abordagem 3 - Algoritmo Union Find (mais avançada)

Ideia

• Cada célula '1' é um nó
• Unir células adjacentes
• Contar quantos pais distintos existem

Quando usar

• Muitas atualizações dinâmicas
• Versões como Number of Islands II

Complexidade

• Tempo: quase O(1) por união (α(n))
• Espaço: O(m · n)

---

Por que “afundar” a ilha funciona?

Ao transformar '1' em '0', garantimos que:

• A ilha será contada apenas uma vez
• Não precisamos de uma matriz extra de visitados

---

Padrões algorítmicos envolvidos

• Flood Fill
• Connected Components
• DFS / BFS
• Union-Find

---

Armadilhas comuns

• Contar diagonais (❌ não permitido)
• Esquecer de marcar como visitado
• Estourar a pilha com DFS em grids grandes
• Modificar o grid quando não é permitido (neste caso, usar visited)

---

Contexto de entrevistas

Esse problema testa:

• Modelagem de grid como grafo
• Escolha entre DFS, BFS ou Union-Find
• Controle correto de estados visitados

---

Generalizações comuns

• Max Area of Island
• Number of Closed Islands
• Surrounded Regions
• Islands em 3D
• Islands com diagonais