플러드 필(재귀)

오늘 나는 첫 번째 Leetcode 그래프 문제인 Flood Fill을 발견했습니다.

다음은 질문입니다.



문제의 목표는 주어진 이미지를 취하는 것입니다. 이 경우:



그리고 특정 픽셀(가운데 빨간색 1)부터 시작하여 이미지를 플러드 필합니다.

기본적으로 그래프의 1을 2로 바꿔야 합니다. 그러나 해당 그래프에 다른 숫자(예: 0)가 있으면 그대로 두어야 합니다.

모든 1을 2로 바꾸면 수정된 이미지를 반환합니다.

이 문제에 어떻게 접근해야 할까요?

한 번에 한 걸음씩 나아가자. 먼저 이 그래프를 순회하려면 재귀를 사용할 수 있음을 인식해야 합니다. 조건이 충족될 때까지 반복하려면 알고리즘 내에 재귀 함수가 필요합니다.

이제 그렇게 했으니 가능한 엣지 케이스를 제거해 보겠습니다.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
};

이미지가 null이면 어떤 변환도 할 수 없다는 것을 알고 있습니다. 그렇다면 이미지를 돌려줍시다. 이미지의 길이가 0이면 이미지가 비어 있으므로 이미지도 반환합니다.

다음으로 시작점을 변수에 저장해야 합니다. 매개변수 image, sr 및 sc를 통해 시작점이 제공됩니다.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
};

sr은 행을 나타내고 sc는 열을 나타냅니다.

재귀 함수

재귀를 시작하기 위해 제공된 매개변수와 시작점 변수인 start를 받는 함수를 만들어 보겠습니다.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
    const fill = (image, r, c, color, initCol) => {}
};

재귀 함수를 사용하려면 기본 사례라고 하는 함수에서 벗어나는 방법이 필요합니다. 기본 사례로 사용할 내용은 다음과 같습니다.

if(r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== initCol) {
     return;
}

r은 행을 나타내고 c는 열을 나타냅니다. 행이 없거나 행 번호가 이미지 길이보다 크면 변환할 수 있는 픽셀이 없습니다. 이는 열에서도 마찬가지입니다.

이제 기본 사례가 설정되었으므로 재귀 논리를 만들 수 있습니다.

모든 코드가 함께 어떻게 생겼는지 빠르게 확인해 봅시다.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
    const fill = (image, r, c, color, initCol) => {
    if(r < 0 || r >= image.length || c < 0 || c >= image[0].length 
        || image[r][c] !== initCol) {
    return;
    }
  }
};

이러한 유형의 문제에는 약간의 트릭이 있는데, 처음에는 명확하지 않지만 작동 방식을 이해하면 완전히 이해됩니다.

가장 먼저 할 일은 설정image[r][c] = -1입니다.

왜요?
기본 사례에서 image[r][c] !== initCol인 경우 반환함을 기억하십시오.

이것으로 우리가 할 수 있는 것은 모든 1을 -1로 바꾸는 것입니다. 그런 다음 재귀 함수를 실행합니다. 순식간에 모든 것이 하나로 합쳐지는 것을 보게 될 것입니다.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
    const fill = (image, r, c, color, initCol) => {
    if(r < 0 || r >= image.length || c < 0 || c >= image[0].length 
        || image[r][c] !== initCol) {
    return;
    }
    image[r][c] = -1;
    fill(image, r-1, c, color, initCol);
    fill(image, r+1, c, color, initCol);
    fill(image, r, c-1, color, initCol);
    fill(image, r, c+1,color, initCol);
  }
};

여기서 재귀 함수를 4번 호출합니다. 문제가 4방향으로 연결된 모든 픽셀을 변경해야 하기 때문입니다. fill()의 각 호출을 살펴보십시오. 첫 번째 실행에서 우리는 이것을 r-1 또는 시작점의 왼쪽에 있는 행에서 호출합니다. if 문(기본 사례)을 누르고 반환하고 1을 -1로 설정하고 다음 fill() 호출을 실행합니다. 이것은 r+1, c-1, c+1에 대해 반복되므로 더 이상 픽셀을 변경할 수 없을 때까지 4방향 모두로 이동하고 시작점을 매번 변경합니다. 이제 모든 1은 -1이고 0은 여전히 ​​남아 있습니다.

재귀 함수를 4번 호출한 후 이 마지막 줄을 함수에 추가합니다. image[r][c] = color;이 작업은 모든 -1을 2로 바꾸는 것입니다.

마지막으로 재귀 함수를 호출한 다음 수정된 이미지를 반환합니다.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    const initCol = image[sr][sc];
    const fill = (image, r, c, color, initCol) => {
        if(r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== initCol) {
            return;
        }
        image[r][c] = -1;
        fill(image, r-1, c, color, initCol);
        fill(image, r+1, c, color, initCol);
        fill(image, r, c-1, color, initCol);
        fill(image, r, c+1,color, initCol);
        image[r][c] = color;
    }
    fill(image, sr, sc, color, initCol)
    return image;
};

이것은 매우 까다로운 질문일 수 있지만 이 문제의 가장 좋은 점은 우리가 4방향 이동을 처리하는 방법이 다른 유사한 문제에 적용될 수 있다는 것입니다!
한 번 시도해보고 화이트보드에 그려보세요. 행운을 빕니다!