[BFS] count islands

count_islands.py

from collections import deque

def count_islands(matrix):
    
    if not matrix:
        return 0
    
    visited = set()
    islands = 0
    
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if(matrix[i][j] == 1) and (i,j) not in visited:
               islands += 1 
               bfs(matrix,i,j,visited)
               
    return islands 

def bfs(matrix,i,j,visited):
    
    directions = [(-1,0),(0,1),(1,0),(0,-1)] # left, up, right, down
    queue = deque([(i,j)])
    visited.add((i,j))
    
    while queue:
        curr_i, curr_j = queue.popleft()
        
        for di,dj in directions:
            ni, nj = curr_i + di, curr_j + dj
            
            if ni < len(matrix) and ni >= 0 and nj < len(matrix[i]) and nj >= 0:
                if (ni, nj) not in visited and matrix[ni][nj] == 1:
                    queue.append((ni, nj))
                    visited.add((ni, nj))

# Example matrix representing islands (1) and water (0)
# matrix_example = [
#     [1, 1, 0, 0, 0],
#     [1, 1, 0, 0, 1],
#     [0, 0, 0, 1, 1],
#     [0, 0, 0, 0, 0],
#     [1, 0, 1, 0, 1]
# ]

matrix_example = [[]]

print("Number of Islands:", count_islands(matrix_example))  # Output: 6