50일 (733. Flood Fill) matrix

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

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 4-directionally 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 0, so 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^16
0 <= sr < m
0 <= sc < n

 

 

- 접근방법

1. image[sr][sc]의 위치의 색을 변수 color로 변경한다.

2. image[sr][sc]와 (상, 하, 좌, 우)에 해당하는 원소들이 기 존의 image[sr][sc]의 색과 같다면 색을 color로 변경한다.

3. (상, 하, 좌, 우) 의 각각 (상, 하, 좌, 우)에 해당하는 원소들이 기존의  image[sr][sc]의 색과 같다면 변수 color로 변경한다.

4. 0<=sr<= image.length-1 그리고 0<=sc<=image[0].length-1 이라는 범위 내에서 3번을 반복한다.

 

 

- 코드

class Solution {

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int value = image[sr][sc]; // 1

        if(color == value) return image; // 2

        helper(image, sr, sc, color, image.length-1, image[0].length-1, value);
        return image;
    }

    private void helper(int[][] image, int sr, int sc, int color, int m, int n, int value) {

        if(sr < 0 || sr > m || sc < 0 || sc > n || image[sr][sc] != value) { // 3
            return;
        }

        image[sr][sc] = color; // 4

        helper(image, sr-1, sc, color, m, n, value); // 5
        helper(image, sr+1, sc, color, m, n, value);
        helper(image, sr, sc-1, color, m, n, value);
        helper(image, sr, sc+1, color, m, n, value);
    }

}

 

1. starting pixel의 기존의 색을 value에 저장한다.

2. 이 조건이 존재하지 않는다면 기존의 색과 변경할 색이 같으므로 무한루프에 빠진다.

3. 상 하 좌 우로 재귀호출을 할 때의 basecase를 설정하였다. (재귀호출 범위를 정하기 위해)

4. 조건에 부합한다면 현재위치의 색이 image[sr][sc]의 원래 색과 같다면 현재위치의 색을 color로 변경한다.

5. 상, 하 , 좌, 우 4방향으로 재귀호출을 한다.

 

 

 

https://leetcode.com/problems/flood-fill/

Flood Fill - LeetCode