[LeetCode] 200. Number of Island(Python/DFS)

내 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])
        di, dj = (1, 0, -1, 0), (0, 1, 0, -1)

        def dfs(i, j):
            grid[i][j] = "0"

            for k in range(4):
                ni, nj = i+di[k], j+dj[k]
                if ni<0 or nj<0 or ni>=n or nj>=m or grid[ni][nj] == '0':
                    continue
                dfs(ni, nj)
        
        answer = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    answer += 1
                    dfs(i, j)

        return answer

교재 풀이

개선점

1. dfs 내부에서 좌표가 유효한지 검사
2. di, dj를 사용하지 않고 dfs함수로 인자를 넘겨주는 과정에서 이동할 좌표값을 바로 넘겨줌

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # if grid is []
        if not grid:
            return 0

        n, m = len(grid), len(grid[0])

        def dfs(i, j):
            if i<0 or i>=n or j<0 or j>=m or grid[i][j] != "1":
                return 
            grid[i][j] = "0"

            dfs(i-1, j)
            dfs(i+1, j)
            dfs(i, j-1)
            dfs(i, j+1)
        
        answer = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    answer += 1
                    dfs(i, j)

        return answer