[LeetCode] 733. Flood Fill - 문제풀이

Description

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 newColor. 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 newColor.

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, newColor = 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, newColor = 2
Output: [[2,2,2],[2,2,2]]

Constraints:

• m == image.length
• n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], newColor < 216
• 0 <= sr < m
• 0 <= sc < n

Solution 1. DFS(Depth-First Search) - 깊이 우선 탐색

private final int[][] DIRECTIONS = new int[][]{{-1,0},{0,1},{1,0},{0,-1}}; 

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {

    if (image[sr][sc] != newColor) { // 같은 값이면 결과 변함없음. 실행하면 서로 계속 전파해서 SOF 발생
        dfs(image, sr, sc, image[sr][sc], newColor);
    }
    return image;
}

public void dfs(int[][] image, int sr, int sc, int color, int newColor){
    if(sr >= 0 && sr < image.length  && sc >= 0 && sc < image[0].length ){
        int currentColor = image[sr][sc];
        if(currentColor == color){ // 현재 컬러가 전달받은 바꾸기 전 컬러와 같으면 새로운 컬러로 채워넣고 4방향 전파
            image[sr][sc] = newColor;
            for(int[] d : DIRECTIONS){ // 시계방향 전파
                dfs(image,sr+d[0],sc+d[1],color,newColor);
            }
        }
    }
}

주어진 시작 지점부터 2차원배열 끝까지 갈때까지 4방향으로 깊이 우선 탐색 재귀호출을 통해 값을 전파합니다.

주의할 점은 newColor가 시작지점과 같으면 결과가 달라지지 않기 때문에 그냥 반환하면됩니다. dfs 재귀호출을 해버리면 계속해서 양옆으로 같은 값을 전파하기 때문에 Stack Overflow를 경험하실 수 있습니다.

• 시간 복잡도: O(N)
• 공간 복잡성: O(N)

Reference

Flood Fill - LeetCode