Why Number of Islands BFS and DFS in DSA C?

The Big Idea

Discover how a simple search method can solve a tricky counting problem in maps!

The Scenario

Imagine you have a big map made of water and land squares. You want to count how many separate islands are on the map. Doing this by looking at each square and trying to remember which land belongs to which island can be very confusing and tiring.

The Problem

Trying to count islands by checking each square manually is slow and easy to mess up. You might count the same island twice or miss some parts because it's hard to track connected land pieces without a clear method.

The Solution

Using BFS (Breadth-First Search) or DFS (Depth-First Search) helps you explore each island fully before moving to the next. These methods automatically find all connected land squares, so you count each island exactly once without confusion.

Before vs After

✗ Before

int countIslands(char **grid, int rows, int cols) {
  int count = 0;
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (grid[i][j] == '1') {
        // manually check neighbors and mark visited
        count++;
      }
    }
  }
  return count;
}

✓ After

void dfs(char **grid, int row, int col, int rows, int cols) {
  if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == '0') return;
  grid[row][col] = '0';
  dfs(grid, row+1, col, rows, cols);
  dfs(grid, row-1, col, rows, cols);
  dfs(grid, row, col+1, rows, cols);
  dfs(grid, row, col-1, rows, cols);
}

int countIslands(char **grid, int rows, int cols) {
  int count = 0;
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (grid[i][j] == '1') {
        dfs(grid, i, j, rows, cols);
        count++;
      }
    }
  }
  return count;
}

What It Enables

This lets you quickly and correctly find how many islands are on any map, no matter how big or complicated.

Real Life Example

Think about a drone flying over a flooded area. It needs to count how many dry land patches (islands) are left to plan rescue missions. BFS or DFS helps the drone's software do this fast and without mistakes.

Key Takeaways

Manual counting is slow and error-prone.

BFS and DFS explore connected land fully to count islands correctly.

This method works well for maps of any size and shape.