733. Flood Fill

💡 풀이

var floodFill = function (image, sr, sc, newColor) {
  let oldColor = image[sr][sc];
  DFS(image, sr, sc, oldColor, newColor);
  return image;
};

var DFS = (image, x, y, oldColor, newColor) => {
  if (
    // 여기 부분!
    x < 0 ||
    y < 0 ||
    x >= image.length ||
    y >= image[x].length ||
    image[x][y] === newColor ||
    image[x][y] !== oldColor
  )
    return;

  image[x][y] = newColor;
  DFS(image, x + 1, y, oldColor, newColor);
  DFS(image, x, y + 1, oldColor, newColor);
  DFS(image, x - 1, y, oldColor, newColor);
  DFS(image, x, y - 1, oldColor, newColor);
};

📝 정리

DFS를 이용한 문제다. 그 동안 DFS, BFS에 대한 이해가 매우 부족해서 관련된 문제를 거의 풀지 못했었는데, 이번에 이 영상을 보고 조금은 더 이해를 한 것 같다. DFS, BFS에 관한 설명은 해당 영상을 보는게 훨씬 이해가 빠를 것이다.

풀이는 다음과 같다.

• image[x][y]를 하나의 node라고 생각해보자.

• image[x][y] = oldColor가 아닌 경우 + 2차원 배열 image의 끝인 부분(위 코드의 주석(!여기부분)을 보자) + image[x][y]가 newColor 인 경우(문제에서는 빨간색) 탐색을 종료한다는 의미이다.

• if문에 걸리는 경우를 제외하고는 4개의 DFS 함수 호출을 통해 재귀적으로 네 방향으로 계속해서 탐색이 이루어진다.

수정, 지적을 환영합니다!

문제 링크

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

LeetCode GitHub

https://github.com/tTab1204/LeetCode