Counting Cells In A Blob

각 픽셀은 background pixel(0)이거나 image pixel(1)이다.

서로 연결된 image pixel들의 집합을 blob이라고 부른다.

8방향으로 연결이 가능하다.

입력 2차원 grid[N][N], 하나의 좌표 x,y

출력 blob의 크기, pixel이 blob에 속하지 않으면 0

현재 픽셀의 blob 크기를 세려면 픽셀이 1이어야한다. 그러므로 1이 아니라면 0을 리턴한다.

픽셀이 1이면 1을 카운트하고 중복 카운트를 방지하기 위해 2를 대입한다.

8방향으로 이웃한 픽셀에 대해 그 픽셀의 좌표를 인자로 갖는 함수를 재귀적으로 호출한다.

s=[
    [1,0,0,0,0,0,0,1],
    [0,1,1,0,0,1,0,0],
    [1,1,0,0,1,0,1,0],
    [0,0,0,0,0,1,0,0],
    [0,1,0,1,0,1,0,0],
    [0,1,0,1,0,1,0,0],
    [1,0,0,0,1,0,0,1],
    [0,1,1,0,0,1,1,1]
]
def CC(x,y):
    n=len(s)
    if x<0 or y<0 or x>=n or y>=n or s[x][y]!=1:
        return 0
    elif s[x][y]:
        s[x][y]=-1
        return 1+CC(x,y+1)+CC(x+1,y+1)+CC(x+1,y)+CC(x+1,y-1)+CC(x,y-1)+CC(x-1,y-1)+CC(x-1,y)+CC(x-1,y+1)
print(CC(0,0))

출력은

5

1

5

13