(Leet Code JS)Flood Fill

https://leetcode.com/problems/flood-fill/

Flood Fill - LeetCode

BFS 알고리즘.

m x n 크기의 visited 배열을 선언하여 false로 초기화.

4 방향을 탐색하기 위한 direct 배열 또한 선언.

color는 image[sr][sc]에 해당하는 숫자로, 탐색을 할 때 해당 숫자와 같으면 newColor로 바꾼다.

 

image[sr][sc] = newColor로 하고,

queue에 [sr, sc] 삽입.

visited[sr][sc]도 true로 바꿔 탐색을 시작한다.

 

큐가 빌 때까지 반복.

x, y 좌표를 queue에서 꺼내고,

4방향을 탐색한다.

 

탐색할 좌표가 배열의 범위를 벗어나지 않고, 방문한 적이 없으며, 해당 좌표의 색깔이 color와 같으면

newColor로 바꿔준다.

또한, 큐에 탐색할 좌표를 넣어주고 visited도 true로 변경하여 계속 탐색을 진행한다.

const floodFill = (image, sr, sc, newColor) => {
    const m = image.length;
    const n = image[0].length;
    const visited = Array.from({length: m}, () => Array(n).fill(false));
    const direct = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const queue = [];
    const color = image[sr][sc];
    
    image[sr][sc] = newColor;
    queue.push([sr, sc]);
    visited[sr][sc] = true;
    
    while(queue.length){
        const [x, y] = queue.shift();
        
        for(let i = 0; i < 4; i++){
            const nx = x + direct[i][0];
            const ny = y + direct[i][1];
            
            if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && image[nx][ny] === color){
                image[nx][ny] = newColor;
                visited[nx][ny] = true;
                queue.push([nx, ny]);
            }
        }
    }
    
    return image;
};