[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]]

👒 Solution

👡 DFS

처음으로 접하는 이 개념을...DFS를 찾아보기만 해서는 어떻게 풀어야 할지 감이 안 잡혀서, 풀이를 하나하나 뜯어보며 풀이방식을 이해하는 것으로 첫번째 DFS풀이를 대신하기로 했다.

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function(image, sr, sc, newColor) {
  const startingColor = image[sr][sc];
  image[sr][sc] = newColor;
  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  const helper = (sr, sc) => {
    for (let direction of directions) {
      const row = sr + d[0];
      const col = sc + d[1];
      if (
        row >= 0 && row < image.length && col >= 0 && col < image[row].length &&
        image[row][col] === startingColor && image[row][col] !== newColor
      ) {
        image[row][col] = newColor;
        helper(row, col);
      }
    }
  };

  helper(sr, sc);
  return image;
};

1. 받아온 시작 노드 sr,sc로 색상을 변경하는 함수를 만든다.
2. directions의 각 배열 direction을 sr과sc에 더해주면 행과 열을 1씩 이동한다.
3. 이동한 곳의 색상은 시작점인 루트노드와 동일할 때만 변경되어야 하고, 새로운 색상으로 변경되지 않은 노드만 변경해주어야 하므로 if문에 조건을 추가해준다.
4. 조건에 해당할 경우 이동한 노드의 색상을 새로운 색상으로 변경한다.
5. 재귀함수를 호출한다. 이때 전달하는 인자는 루트노드가 아닌 방금 변경한 노드이다.
   변경한 노드로부터 또 다시 이동해 근접한 노드의 색상을 변경해야하기 때문이다.
6. if문 조건에 맞게 바꿀 노드가 없어지면, 즉 모든 노드의 색상을 바꾸면 최종적으로 image를 리턴해준다.

👡 BFS

var floodFill = function(image, sr, sc, newColor) {
let directions = [ [-1, 0], [1,0], [0, -1], [0, 1] ];
let height = image.length;
let width = image[0].length;

fillNeighbour( [[sr,sc]], image[sr][sc] , newColor );
return image;

function fillNeighbour(queue, oldColor, newColor) {
    while(queue.length > 0){
        let [a, b] = queue.shift();
        image[a][b] = newColor;

        directions.map((direction) => {
            let [m,n] = direction;
            let x = a+m;
            let y = b+n;
            
            if( x >=0 && y >= 0 && x < height && y < width 
               && image[x][y] === oldColor && image[x][y]  !== newColor ) {
                queue.push([x, y]);  
            }
        });
    }
}
};

1. queue에는 시작노드 [sr,sc]가 먼저 할당된다.
2. 이 queue에서 노드를 빼와 새로운 색상으로 변경한다.
3. 각 direction을 더해 이동지점의 노드들을 queue에 넣는다. queue는 앞으로 색상을 변경할 노드를 넣어둔 것이기 때문에, 이 때 조건은 이전 색상과 같고 새로운 색상이 아닌 노드들이다.
4. queue에 아무것도 남지 않을 때까지 계속해서 노드를 빼와 새로운 색상으로 변경한다.

Reference

• https://leetcode.com/problems/flood-fill/discuss/1286722/JS-Solution-DFS-Faster-than-97
• https://leetcode.com/problems/flood-fill/discuss/1550843/JS-or-BFS