733. Flood Fill (홍수 채우기)

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.

 

이미지는 m x n 정수 그리드  image로 표현되며 여기서 image[i][j]는 이미지 픽셀 값을 나타냅니다.

또한 세 개의 정수  sr, sc 및 color가 제공됩니다. 픽셀 image[sr][sc]에서 시작하여 이미지에 플러드 필을 수행해야 합니다.

플러드 필을 수행하려면 시작 픽셀과 시작 픽셀과 동일한 색상의 시작 픽셀에 4방향으로 연결된 픽셀, 그리고 해당 픽셀에 4방향으로 연결된(동일한 색상)을 고려합니다. 앞서 언급한 모든 픽셀의 색상을 color로 바꿉니다.

플러드 필을 수행한 후 수정된 이미지를 반환합니다.

 

예시 1:

입력: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
출력: [[2,2,2],[2,2,0],[2,0,1]]
설명: 위치가 (sr, sc) = (1, 1)인 이미지의 중앙(즉, 빨간색 픽셀)부터 시작 픽셀(즉, 파란색 픽셀)과 동일한 색상의 경로로 연결된 모든 픽셀에 색상이 새로운 색상으로 지정됩니다.
하단 모서리는 시작 픽셀에 4방향으로 연결되어 있지 않기 때문에 색상이 2가 아닙니다.

 

예시 2:

입력: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
출력: [[0,0,0],[0,0,0]]
설명: 시작 픽셀은 이미 0으로 표시되어 있으므로 이미지가 변경되지 않습니다.

 

조건:

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

정답:

public class Solution
{
    public int[][] FloodFill(int[][] image, int sr, int sc, int color)
    {
        if (image[sr][sc] == color)
        {
            return image;
        }
        fill(image, sr, sc, image[sr][sc], color);
        return image;
    }

    public void fill(int[][] image, int y, int x, int color, int newColor)
    {
        int h = image.Length;
        int w = image[0].Length;

        if (0 <= y && y < h && 0 <= x && x < w &&  image[y][x] == color)
        {
            image[y][x] = newColor;
            fill(image, y - 1, x, color, newColor);
            fill(image, y + 1, x, color, newColor);
            fill(image, y, x - 1, color, newColor);
            fill(image, y, x + 1, color, newColor);
        }
    }
}

해설: 

해당 위치의 color가 다를때만 fill을 실행하여 네 방향을 모두 탐색하고  색을 바꿔주었습니다.