Finding the number of islands using DFS. A group of connected 1s form an island. (https://www.geeksforgeeks.org/find-number-of-islands/)

Count Islands (DFS).py

#!/usr/bin/env python3


def is_safe(x, y, matrix, visited):
	col = len(visited[0])
	row = len(visited)

	if x >= 0 and y >= 0 and x < col and y < row and visited[y][x] == False and matrix[y][x] == 1:
		return True
	else:
		return False


def dfs(x, y, matrix, visited):
	neighbors = [(1,0),(0,-1),(-1,0),(0,1)]

	visited[y][x] = True

	for k in range(len(neighbors)):
		if is_safe(x + neighbors[k][0], y + neighbors[k][1], matrix, visited):
			dfs(x + neighbors[k][0], y + neighbors[k][1], matrix, visited)


def number_of_islands(x, y, matrix, visited):
	col = len(matrix[0])
	row = len(matrix)

	count = 0
	
	for i in range(row):
		for j in range(col):
			if is_safe(i, j, matrix, visited):
				dfs(i, j, matrix, visited)  # find neighboring land by dfs
				count += 1  # increase count if no more islands found in vicinity using dfs

	return count


def main():
	'''
		[[1, 1, 0, 0, 0],
         [0, 1, 0, 0, 1],
         [1, 0, 0, 1, 1],
         [0, 0, 0, 0, 0],
         [1, 1, 1, 0, 1]]
	'''
	matrix = [[1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 0, 0, 0], [1, 1, 1, 0, 1]]

	col = len(matrix[0])
	row = len(matrix)

	visited = [[False for i in range(col)] for j in range(row)]

	print(number_of_islands(0, 0, matrix, visited))


if __name__ == '__main__':
	main()