[PYTHON] Leet Code "200. Number of Islands" commentary

Overview

It seems that many foreign-affiliated companies conduct coding tests in interviews with engineers. The site of the past question of the coding test is Let Code I don't plan to take it, but I solve one question every day for studying

problem

200. Number of Islands Difficulty is Medium

You will be given the following input In a map-like image, 1 represents land and 0 represents the sea. An island is created on adjacent land The output required is the number of islands In the example below, there are 3 islands in the upper left, middle and lower right, so 3 is the output


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

Look from the edge and repeat the following

  1. If you find an island, mark all the land on that island as visited
  2. Add 1 island counter

python


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        #Make all the land on the island visited
        def check(i,j):            
            if grid[i][j]=="1":        
                #Make it visited
                grid[i][j]="2"                
                #Recursively visit adjacent lands on the top, bottom, left, and right
                if i-1>=0:
                    check(i-1,j)
                if j-1>=0:
                    check(i,j-1)
                if i+1<=len(grid)-1:
                    check(i+1,j)
                if j+1<=len(grid[0])-1:
                    check(i,j+1)                                            
        
        #Island counter
        count=0
            
        #grid[0][0]I will look at it in order from
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #If it was land
                if grid[i][j]=="1":
                    #Make all the land on the island visited
                    check(i,j)
                    #Add 1 island counter
                    count+=1                
        return count
                

Recommended Posts

Leet Code "200. Number of Islands" commentary
leet code Palindrome Number (easy)
Let Code Day87 Starting from Zero "1512. Number of Good Pairs"
10. Counting the number of lines
Get the number of digits
Explain the code of Tensorflow_in_ROS
Calculate the number of changes