LeetCode 733 - Flood Fill (Easy)

💡 문제

LeetCode - 733번

🎯 풀이 과정

BFS 를 이용해서 도달 가능한 모든 지점을 확인하는 문제입니다.
여기서 visit 이라는 2차원 배열을 유지하며 중복 방문을 검사함과 동시에 도달 가능한 위치를 기록합니다.

👨‍💻 코드

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, newColor) {
  const dr = [0, 0, 1, -1]
  const dc = [1, -1, 0, 0]
  const [ROW, COL] = [image.length, image[0].length]

  function outOfRange(r, c) {
    return r < 0 || r >= ROW || c < 0 || c >= COL
  }

  function bfs(sr, sc) {
    const queue = []
    const visit = Array.from(Array(ROW), () => Array(COL).fill(false))

    queue.push([sr, sc])
    visit[sr][sc] = true

    while (queue.length > 0) {
      const [hr, hc] = queue.shift()

      for (let dir = 0; dir < 4; dir += 1) {
        const [nr, nc] = [hr + dr[dir], hc + dc[dir]]
        if (outOfRange(nr, nc) || visit[nr][nc]) {
          continue
        }

        if (image[hr][hc] !== image[nr][nc]) {
          continue
        }

        queue.push([nr, nc])
        visit[nr][nc] = true
      }
    }

    return visit
  }

  const reachable = bfs(sr, sc)
  const answer = Array.from(Array(ROW), () => Array(COL).fill(0))

  for (let row = 0; row < ROW; row += 1) {
    for (let col = 0; col < COL; col += 1) {
      if (reachable[row][col]) {
        answer[row][col] = newColor
      } else {
        answer[row][col] = image[row][col]
      }
    }
  }

  return answer
}