[LeetCode/JavaScript] 733. Flood Fill (easy)

 

문제 

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 < 2^16
• 0 <= sr < m
• 0 <= sc < n

 

 

코드

var floodFill = function(image, sr, sc, newColor) {
    let color = image[sr][sc];
    image[sr][sc] = -1;
    isConnected(image, sr, sc, color, -1);
    for(let i=0; i<image.length; i++) {
        for(let j=0; j<image[0].length; j++) {
            if(image[i][j] == -1) 
                image[i][j] = newColor;
        }
    }
    return image;
};

function isConnected(image, row, col, color, setColor) {
    if(row+1<image.length && image[row+1][col] == color) {
        image[row+1][col] = setColor;
        isConnected(image, row+1, col, color, setColor);
    }
    if(row-1>=0 && image[row-1][col] == color) {
        image[row-1][col] = setColor;
        isConnected(image, row-1, col, color, setColor);
    }
    if(col+1<image[0].length && image[row][col+1] == color) {
        image[row][col+1] = setColor;
        isConnected(image, row, col+1, color, setColor);
    }
    if(col-1>=0 && image[row][col-1] == color) {
        image[row][col-1] = setColor;
        isConnected(image, row, col-1, color, setColor);
    }
}

참고

원래  isConnected 함수에서 setColor에 newColor를 넣었었는데, newColor가 기존 color랑 같은 경우가 있었다. 

그런 경우에 무한 탐색을 하여 RangeError: Maximum call stack size exceeded로 인한 Runtime Error가 났고, 이를 해결하기 위해 isConnected에서 setColor를 -1로 하고, 탐색이 끝난 뒤에 반복문으로 값이 -1인 경우에 newColor로 변경해주었다. 

 

문제는 해결했지만 더 효율적인 방법을 찾아봐야겠다.