200. Number of Islands

DFS(재귀)를 이용한 문제 풀이 

 

좌표를 찾아가다가 1을 만나면 연결된 1을 0으로 만들고 상,하,좌,우에 1이 없을때까지 반복

 

내부함수로 구현했지만, dfs를 함수로 빼도되지만, self와 grid를 넘기기 싫어서 이렇게 구현함

    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(x:int, y:int)->int:
            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != '1':
                return 0
            grid[x][y] = 0
            dfs(x+1, y)
            dfs(x-1, y)
            dfs(x, y+1)
            dfs(x, y-1)
            return 1
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                count += dfs(i, j)
        return count