Island Counter - 2D Grid Traversal

mediumPython

Lesson

Graph Traversal and Connected Components

When working with 2D grids, many problems can be solved by thinking of them as graphs. Each cell in the grid is a node, and adjacent cells (usually horizontally and vertically adjacent) are connected by edges. This transforms grid problems into graph traversal problems.

Connected Components are groups of nodes that are all reachable from each other through a series of edges. In a 2D grid context, a connected component might represent an island of land cells, a region of similar colors, or any group of cells that share some property and are adjacent to each other.

To find connected components, we use graph traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS). The key insight is that when we find an unvisited node that belongs to a component we're interested in, we need to explore all nodes connected to it and mark them as visited.

The general algorithm for counting connected components is:

  1. Iterate through each cell in the grid
  2. When you find an unvisited cell that matches your criteria (like a land cell)
  3. Increment your component counter
  4. Use DFS/BFS to visit all connected cells and mark them as processed
  5. Continue until you've checked every cell

This approach ensures that each connected component is counted exactly once, because once we've found and explored a component, all its cells are marked as visited.

DFS vs BFS: Both work equally well for this type of problem. DFS is often easier to implement recursively and uses less memory for wide, shallow components. BFS uses a queue and can be better for very deep components to avoid stack overflow.

Example
1def count_regions(grid, target_value): 2 """Count connected regions of cells with target_value""" 3 if not grid or not grid[0]: 4 return 0 5 6 rows, cols = len(grid), len(grid[0]) 7 visited = [[False] * cols for _ in range(rows)] 8 count = 0 9 10 def dfs(r, c): 11 # Check boundaries and if cell matches criteria 12 if (r < 0 or r >= rows or c < 0 or c >= cols or 13 visited[r][c] or grid[r][c] != target_value): 14 return 15 16 visited[r][c] = True 17 # Explore all 4 directions 18 dfs(r-1, c) # up 19 dfs(r+1, c) # down 20 dfs(r, c-1) # left 21 dfs(r, c+1) # right 22 23 for r in range(rows): 24 for c in range(cols): 25 if grid[r][c] == target_value and not visited[r][c]: 26 count += 1 27 dfs(r, c) 28 29 return count
L12Base case: stop if out of bounds, already visited, or doesn't match target
L15Mark current cell as visited to avoid counting it again
L23Found new unvisited region - increment counter and explore it completely

Key Takeaways

  • •2D grid problems often become graph traversal problems where cells are nodes and adjacency defines edges
  • •Connected components are found by exploring from each unvisited qualifying cell using DFS or BFS
  • •Always mark visited cells to ensure each component is counted exactly once
Loading...