[알고리즘] LeetCode Flood Fill

1. 개요

전형적인 DFS 문제로 시작점이 주어지는데 시작점의 숫자와 같은 숫자들을 계속 확산하면서 바꿔주는 문제이다.

다시 정리하면 시작점의 상하좌우에서 시작점과 같은 숫자가 있다면 color라는 변수의 숫자로 바꿔주고 또 바뀐 문자의 상하좌우를 확인해서 바꿔주는 그런 문제이다.

Flood Fill - LeetCode

 

 

2. 풀이

DFS 문제라는 걸 바로 알았는데 실제 구현을 이상하게 했다.

m x n을 헷갈리지않나 if문을 달아서 탐색이 제대로 되지 않아 NaN에러가 뜨는 등 문제가 많았다.

그래서 그냥 코드를 갈아엎고 조건을 다시 제대로 읽어보고 매번 구현하는 방식으로 구현했더니 바로 풀렸다.

var floodFill = function (image, sr, sc, color) {
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  const m = image.length;
  const n = image[0].length;
  const target = image[sr][sc];

  if (target === color) return image;

  function DFS(cx, cy) {
    for (let i = 0; i < dx.length; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && image[nx][ny] === target) {
        image[nx][ny] = color;
        DFS(nx, ny);
      }
    }
  }

  image[sr][sc] = color;
  DFS(sr, sc);

  return image;
};

console.log(
  floodFill(
    [
      [0, 0, 0],
      [0, 1, 0],
    ],
    0,
    0,
    2
  )
);JAVASCRIPT