[Leetcode/DFS, BFS, Matrix] 733. Flood Fill

 

Depth-First Search (DFS)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original_color = image[sr][sc]
        if original_color == color:
            return image  # No need to do anything if the target color is the same
        
        rows, cols = len(image), len(image[0])
        
        def dfs(r, c):
            if (r < 0 or r >= rows or c < 0 or c >= cols): # 좌표가 2차원 격자를 벗어낫을때
                return # 함수를 종료시킨다
            if image[r][c] != original_color:
                return
            
            image[r][c] = color  # Change color
            
            # Visit 4-directionally
            dfs(r + 1, c) # 상
            dfs(r - 1, c) # 하
            dfs(r, c + 1) # 좌
            dfs(r, c - 1) # 우
        
        dfs(sr, sc)
        return image

 

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        R, C = len(image), len(image[0])
        color = image[sr][sc]
        if color == newColor:
            return image
        def dfs(r, c):
            if image[r][c] == color:
                image[r][c] = newColor
                if r >= 1:
                    dfs(r-1, c)
                if r + 1 < R:
                    dfs(r + 1, c)
                if c >= 1:
                    dfs(r, c - 1)
                if c + 1 < C:
                    dfs(r, c + 1)

        dfs(sr, sc)
        return image

Breadth-First Search (BFS)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        gridRowSize = len(image)
        gridColSize = len(image[0])
        prevColor = image[sr][sc]

        if prevColor == color:
            return image

        moves = [(1, 0), (-1, 0), (0, 1), (0, -1)] # Key
        q = deque()
        q.append((sr, sc))

        while q:
            r, c = q.popleft()
            image[r][c] = color

            for dr, dc in moves:
                nr, nc = r + dr, c + dc
                if (0 <= nr < gridRowSize and 0 <= nc < gridColSize and 
                    image[nr][nc] == prevColor):
                    q.append((nr, nc))
        
        return image