DFS, 색깔 칠하기 (floodFill) 알고리즘

김민아·2023년 1월 17일
0

733. Flood Fill

733. Flood Fill

문제

테스트 케이스

Input: 
  image = [[1,1,1],[1,1,0],[1,0,1]], 
  sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

기본적인 DFS 알고리즘을 이용하는 문제이다. 시작점 ij가 주어지고 이웃한 상하좌우를 탐색하여 동일한 색상을 업데이트한다. 이웃한 모든 셀을 방문할 때까지 재귀적으로 탐색한다.

풀이

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} color
 * @return {number[][]}
 */
var floodFill = function(image, sr, sc, color) {
  let m = image.length;
  let n = image[0].length;
  let start = image[sr][sc];

  function dfs (r, c) {
    // r과 c가 범위 안에 있거나 탐색할 셀이 이미 color와 같으면 return
    if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] === color) {
      return 
    }

    if (image[r][c] === start) {
      // 새로운 셀에 color로 바꾸고 
      image[r][c] = color;
      // 상하좌우 순으로 탐색
      dfs(r - 1, c)
      dfs(r + 1, c)
      dfs(r, c - 1)
      dfs(r, c + 1)
    }
  };

  dfs(sr, sc) // 1, 1
  
  return image;
};

0개의 댓글