200. Number of Islands

Medium

Problem:

Given a 2D grid map where 1 represents land and 0 represents water, calculate the number of islands (determine the number of connected groups of 1s).

Input:
  11110
  11010
  11000
  00000
Output: 1

Input:
  11000
  11000
  00100
  00011
Output: 3

https://leetcode.com/problems/number-of-islands/

Solution:

DFS

By completing the search in each of the four directions using DFS recursion, we can determine the number of lands by incrementing 1.

1. Here, based on the input value 'grid', we search row by row and column by column for land (1). When land is discovered, we initiate the search by calling the dfs() function.

2. At this time, the places that have been visited are marked with a value other than 1. This ensures they aren't recalculated in subsequent iterations. It's a form of pruning.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
       if not grid:
            return 0
            
        def dfs(i, j):
            # If it's no longer a land, exit
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
                return
            grid[i][j] = 0
            
            # Search north, south, east and west
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)       

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    # After searching all the lands, increase count
                    count += 1
        return count

BFS

Reference: https://www.youtube.com/watch?v=pV2kpPD66nE

import collections

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # Exception
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        visit = set()
        islands = 0
        
        def bfs(r, c):
            q = collections.deque()
            visit.add((r, c))
            q.append((r, c))
            while q:
                row, col = q.popleft() # DFS -> q.pop()
                directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    if (r in range(rows) and c in range(cols) and grid[r][c] == "1" and (r, c) not in visit):
                        q.append((r, c))
                        visit.add((r, c))
                    
        for r i range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visit:
                    bfs(r, c)
                    islands += 1
                    
        return islands