# Tree - Number of Islands

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

BFS

## Problem

Given an `m x n`

2D binary grid `grid`

which represents a map of `'1'`

s (land) and `'0'`

s (water), return *the number of islands*. An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

**Example 1:**

1
2
3
4
5
6
7

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

**Example 2:**

1
2
3
4
5
6
7

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

## Solution

This is a very simple BFS solution. We need to start at every cell of the grid (if its already not visited), then run bfs and flag each visited cells.

Start by defining the required variables.The `directions`

variable is for traversing in 4 directions.

1
2
3

ROWS, COLS =len(grid), len(grid[0])
visited = set()
directions = [[0,1], [0,-1], [1, 0], [-1, 0]]

Now define the `bfs()`

function. Very important is to add to `visited`

right after inserting into the `queue`

.

1
2
3
4
5
6
7
8
9
10
11
12
13

def bfs(row, col):
queue = collections.deque()
queue.append((row, col))
while queue:
row, col = queue.popleft()
for dr, dc in directions:
nei_row, nei_col = row+dr, col+dc
if nei_row < 0 or nei_row == ROWS or nei_col < 0 or nei_col == COLS:
or (nei_row,nei_col) in visited or grid[nei_row][nei_col]=='0':
continue
visited.add((nei_row, nei_col))
queue.append((nei_row, nei_col))

Once the `bfs()`

function is completed, we need to run it for all the cells.

1
2
3
4
5
6
7

result = 0
for row in range(ROWS):
for col in range(COLS):
if (row,col) not in visited and grid[row, col]=='1':
bfs(row,col)
result+=1
return result

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def num_islands(grid) -> int:
ROWS, COLS = len(grid), len(grid[0])
visited = set()
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def bfs(row, col):
queue = collections.deque()
queue.append((row, col))
while queue:
row, col = queue.popleft()
for dr, dc in directions:
r = row+dr
c = col+dc
if r < 0 or r == ROWS or c < 0 or c == COLS or (r, c) in visited or grid[r][c] == '0':
continue
queue.append((r, c))
visited.add((r, c))
result = 0
for r in range(ROWS):
for c in range(COLS):
if (r, c) not in visited and grid[r][c] == '1':
bfs(r, c)
result += 1
return result