LeetCode「200. Number of Islands」解説

概要

外資系では、エンジニアの面接でコーディングテストを行う企業が多いらしいです
そのコーディングテストの過去問のサイトがLeetCodeです
受ける予定はありませんが、勉強のために毎日1問解いています

問題

200. Number of Islands
難易度はMediumです

以下のような入力が与えられます
地図みたいなイメージで、1が陸、0が海を表します
隣接した陸で1つの島が作られます
求められる出力は、島の数です
以下の例では、左上、真ん中、右下に3つの島があるので、3が出力です

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

解法

端から順に見ていって、以下を繰り返します
1. 島を見つけたら、その島の陸を、全て訪問済みにする
2. 島カウンターを1足す

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        #島の陸を全て訪問済みにする
        def check(i,j):            
            if grid[i][j]=="1":        
                #訪問済みにする        
                grid[i][j]="2"                
                #上下左右の隣接した陸を、再帰的に訪問済みにする
                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)                                            

        #島カウンター
        count=0

        #grid[0][0]から順に見ていく
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #陸だったら
                if grid[i][j]=="1":
                    #島の陸を全て訪問済みにする
                    check(i,j)
                    #島カウンター1足す
                    count+=1                
        return count