[Leetcode] 200. Number of Islands

문제 바로가기

BFS

Time Complexity: $O(n_r n_c)$
Space Complexity: $O(n_r n_c)$

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        stack = list()
        total_r = len(grid)
        total_c = len(grid[0])
        res = 0
        
        def bfs(r: int, c: int) -> None:
            grid[r][c] = ""
            stack.append((r, c))
            while stack:
                r, c = stack.pop()
                for nR, nC in [(r+1, c), (r, c+1), (r-1, c), (r, c-1)]:
                    if 0 <= nR < total_r and 0 <= nC < total_c and grid[nR][nC] == "1":
                        grid[nR][nC] = ""
                        stack.append((nR, nC))
        
        for r in range(total_r):
            for c in range(total_c):
                if (grid[r][c] == "1"):
                    bfs(r, c)
                    res += 1
        # grid 복구
        for r in range(total_r):
            for c in range(total_c):
                if (not grid[r][c]):
                    grid[r][c] = "1"
        return res

DFS

Time Complexity: $O(n_r n_c)$
Space Complexity: $O(n_r n_c)$

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        total_r = len(grid)
        total_c = len(grid[0])
        visited = [[False]*total_c for _ in range(total_r)]
        res = 0
        
        def dfs(r, c):
            visited[r][c] = True
            for nR, nC in [(r+1, c), (r, c+1), (r-1, c), (r, c-1)]:
                if 0 <= nR < total_r and 0 <= nC < total_c \
                and grid[nR][nC] == "1" and not visited[nR][nC]:
                    dfs(nR, nC)

        for r in range(total_r):
            for c in range(total_c):
                if (grid[r][c] == "1" and not visited[r][c]):
                    dfs(r, c)
                    res += 1
        return res