[DFS][JavaScript][LeetCode] #733. Flood Fill

#DFS  #EASY

Flood Fill - LeetCode

🌷 문제 설명

✏️ LeetCode 연습문제: Flood Fill
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 color. 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 color.
Return the modified image after performing the flood fill.

🎃 제한 사항
m == image.length
n == image[i].length
1 <= m, n <= 500 <= image[i][j], color < 2^16
0 <= sr < m
0 <= sc < n

입출력 예

nums	sr	sc	color	result
[[1,1,1],[1,1,0],[1,0,1]]	1	2	2	[[2,2,2],[2,2,0],[2,0,1]]
[[0,0,0][0,0,0]]	0	0	0	[[0,0,0][0,0,0]]

 

🌷 내 코드

1. 재귀 사용

var floodFill = function(image, sr, sc, color) {
    if (image[sr][sc] == color) return image;
    fill(image, sr, sc, color, image[sr][sc])
    return image
};

var fill = function(image, sr, sc, color, currPos) {
    if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length) return;

    if (currPos !== image[sr][sc]) return;
    image[sr][sc] = color;
    fill (image, sr+1, sc, color, currPos)
    fill (image, sr-1, sc, color, currPos)
    fill (image, sr, sc+1, color, currPos)
    fill (image, sr, sc-1, color, currPos)
}

2. 스택 사용(Boolean)

const floodFill = (image, sr, sc, newColor) => {
  const stack = [[sr, sc]];
  const color = image[sr][sc];
  while (!!stack.length) {
    const [r, c] = stack.pop();
    if (image[r][c] === newColor) continue;
    if (image[r + 1]?.[c] === color) stack.push([r + 1, c]);
    if (image[r - 1]?.[c] === color) stack.push([r - 1, c]);
    if (image[r][c + 1] === color) stack.push([r, c + 1]);
    if (image[r][c - 1] === color) stack.push([r, c - 1]);
    image[r][c] = newColor;
  }
  return image;
};

3. 스택 사용(length)

뭐가 달라졌는지 맞춰보세욤 정답은 코멘트에!

const floodFill = (image, sr, sc, newColor) => {
  const stack = [[sr, sc]];
  const color = image[sr][sc];
  while (stack.length) {
    const [r, c] = stack.pop();
    if (image[r][c] === newColor) continue;
    if (image[r + 1]?.[c] === color) stack.push([r + 1, c]);
    if (image[r - 1]?.[c] === color) stack.push([r - 1, c]);
    if (image[r][c + 1] === color) stack.push([r, c + 1]);
    if (image[r][c - 1] === color) stack.push([r, c - 1]);
    image[r][c] = newColor;
  }
  return image;
};

 

🌷 코멘트

DFS.. 설명하기 참 애매한테 뭔가 패턴은 있어서 어떻게 어떻게 때려맞추게 되는 마성의 탐색법(말로 쓰기 너무 애매해서 지금 DFS 포스팅이 늦어지는 중).

보통 재귀가 더 느리지 않나? 1초 차이인거 보면 LeetCode문제인거 같기두하고,,

정답은 while 조건문 입니당 첫번째는 '!!'로 true, false판단하구 두번째는 길이값이 나옴!

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview