733. Flood Fill

Description

You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill:

1. Begin with the starting pixel and change its color to color.
2. Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel.
3. Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel.
4. The process stops when there are no more adjacent pixels of the original color to update.

Return the modified image after performing the flood fill.

Example 1:

• Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
• Output: [[2,2,2],[2,2,0],[2,0,1]]
• Explanation:
  
  From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
  Note the bottom corner is not colored 2, because it is not horizontally or vertically connected to the starting pixel.

Example 2:

• Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
• Output: [[0,0,0],[0,0,0]]
• Explanation:
  The starting pixel is already colored with 0, which is the same as the target color.
  Therefore, no changes are made to the image.

Constraints:

• m == image.length
• n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], color < 2¹⁶
• 0 <= sr < m
• 0 <= sc < n

💡 Hint 1:
Write a recursive function that paints the pixel if it's the correct color, then recurses on neighboring pixels.

Submitted Code

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """
        self.rows = len(image)              # 행 개수
        self.cols = len(image[0])           # 열 개수
        self.target_color = image[sr][sc]   # 바꿔야 하는 숫자

        def search(r, c):
            if image[r][c] != self.target_color:
                return
            
            # 값이 target_color라면 color로 변경 후 4방향 체크
            image[r][c] = color

            if r > 0: search(r-1, c)            # 위
            if r < self.rows-1: search(r+1, c)  # 아래
            if c > 0: search(r, c-1)            # 왼쪽
            if c < self.cols-1: search(r, c+1)  # 오른쪽

        if self.target_color != color:          # (sr, sc)의 값이 color와 같다면 호출 필요 없음
            search(sr, sc)
        return image

Runtime: 0 ms | Beats 100.00%
Memory: 12.77 MB | Beats 26.64%

특정한 색이 끊기지 않고 연결된 부분에만 새로운 색을 칠해야 하는 문제로, DFS를 사용했다.

Other Solutions

1st

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        
        start_color = image[sr][sc]                 # color로 바꿔야 할 값
        
        def flood_fill(x, y):
            if x < 0 or x >= len(image): return     # 행 범위 벗어나면 리턴
            if y < 0 or y >= len(image[0]): return  # 열 범위 벗어나면 리턴
            
            if image[x][y] == color: return         # 이미 color와 같은 값이면 리턴
            if image[x][y] != start_color: return   # 값이 start_color와 다르면 리턴
            
            image[x][y] = color
            
            flood_fill(x-1, y)
            flood_fill(x+1, y)
            flood_fill(x, y+1)
            flood_fill(x, y-1)
        
        flood_fill(sr, sc)
        return image

time complexity: 𝑂(𝑚*𝑛)
space complexity: 𝑂(𝑚*𝑛)

재귀 호출에 해당하지 않는 조건들을 먼저 모두 체크해서 리턴시키는 방법도 있다.

2nd

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        original = image[sr][sc]

        if original == color:
            return image

        seen = set()
        self.checkNeighbors(image, original, color, sr, sc, seen)
        return image

    def checkNeighbors(self, image, original, new, r, c, seen):
        seen.add((r, c))
        image[r][c] = new
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < len(image) and 0 <= nc < len(image[0]) and 
                image[nr][nc] == original and (nr, nc) not in seen):
                self.checkNeighbors(image, original, new, nr, nc, seen)
        

set()에 이미 방문했던 셀을 저장해서 중복 순회를 막을 수도 있다.