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 알고리즘을 이용하는 문제이다. 시작점 i
와 j
가 주어지고 이웃한 상하좌우를 탐색하여 동일한 색상을 업데이트한다. 이웃한 모든 셀을 방문할 때까지 재귀적으로 탐색한다.
/**
* @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;
};