Recursion - blob 구하기

blob구하기

blob이란 binary이미지에서 서로 연결된 이미지들

[1,1,0,0,1]
[1,1,0,0,1]
[0,0,0,0,1]
[1,1,0,0,0]

이 2차원 배열에 1이 이미지,0이 이미지가 아님을 표현하고 있다고 가정한다면

왼쪽 위의 blob의 크기는 4, 오른쪽은 3, 왼쪽 아래는 2가 된다

접근 방법

시작 좌표에서 시작하고 처음 탐색 길이를 1로 설정한 후에

처음엔 자기 자신만 그 뒤엔 2x2크기의 정사각형의 변에 있는 이미지를 카운팅

그 뒤엔 3x3크기의 정사각형 크기의 변에 있는 이미지를 카운팅해가면서 이미지를 카운팅하는식으로 구현하려했다

근데 이러면 정사각형으로만 탐색이 되기 때문에 이미지가 예쁘게 그려지지 않았다면 탐색이 불가능해진다

그래서 미로 탐색과 비슷한 방법으로 구현해보기로 했다

1. 자기 자신을 검사한 후 이미지라면 4방향이 아닌 8방향으로 재귀 호출

2. 호출 횟수가 많아질 것 같아서 호출한 뒤 검사가 아닌 검사 후 호출
   하려 했으나.. 조건 검사 코드가 너무 많아져서 일단 호출후에 검사하는 방식으로 짜려한다

내가 푼 코드

function countingBlob(x, y) {

    if(x<0||y<0||x>=binaryImage.length||y>=binaryImage.length){
        return 0;
    }

    if(binaryImage[x][y]!==1) return 0;

    binaryImage[x][y] = -1;

    return  1+countingBlob(x+1,y) + countingBlob(x-1,y) + countingBlob(x, y+1) + countingBlob(x,y-1)
            + countingBlob(x+1,y+1) + countingBlob(x-1,y-1) + countingBlob(x-1, y+1) + countingBlob(x+1,y-1)
}

좌표를 받아서 좌표에서 부터 blob을 구하는 함수

이미지 배열 밖으로 넘어가면 0을 반환

이미지가 아니라면 0을 반환하고

이미지라면 이후 현재 타일을 재방문하는 것을 막기 위해서 현재 이미지를 -1로 바꿔주고

주변의 타일들이 이미지인지 확인하기 위해 8방향으로 재귀 호출한 뒤에 +1을 해준다