200. Number of Islands ( 섬의 개수 )

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        def dfs(x,y):
            if x < 0 or y < 0 or x>= len(grid) or y>= len(grid[0]) : 
                return False 
            
            if grid[x][y] == "1" :
                grid[x][y] = 0 
                
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y+1)
                dfs(x,y-1)
                
                return True
            return False 
        
        cnt = 0 
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if dfs(x,y) == True:
                    cnt += 1 
        return cnt

 

음료수 얼려 먹기 문제와 거의 유사한 dfs 문제이다. 

입력 받는 방식이 조금 특이하다. 

 

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

 

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

Number of Islands - LeetCode