[JAVA] Recursion 응용: Counting Cells in a Blob

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

흑백으로 구성된 Binary 이미지에서, 서로 연결된 image pixel의 집합을 blob이라고 합니다. 이번 포스팅의 제목인 Counting cells in a blob은, Binary 이미지에서 임의의 한 점으로부터 그 점이 포함된 Blob의 크기를 구하는 작업을 의미합니다.

---

Recursive Solution

Blob의 count를 계산하는 방법 역시 Recursion을 이용합니다.

위의 그림과 같이 하나의 좌표가 주어졌을 때, 그 픽셀을 둘러싸는 8개의 픽셀들을 대상으로 blob을 COUNT 하는 함수를 재귀 호출하고, count 한 cell에 대해서는 색을 바꿔 이후에 중복으로 count 되는 걸 방지합니다.

public class CountCell {
    private static int BACKGROUND_COLOR =0;
    private static int IMAGE_COLOR=1;
    private static int ALREADY_COUNTED =2;

    private static int N= 8;
    private static int[][] grid = {
            {0,0,0,0,0,0,0,1},
            {0,1,1,0,1,1,0,1},
            {0,0,0,1,0,0,0,1},
            {0,1,0,0,1,1,0,0},
            {0,1,1,1,0,0,1,1},
            {0,1,0,0,0,1,0,1},
            {0,0,0,1,0,0,0,1},
            {0,1,1,1,0,1,0,0}
    };

    public int countCells(int x, int y){
        if(x<0||x>=N || y<0 || y>=N)	// 좌표 x,y 의 유효성 검증
            return 0;
        else if(grid[x][y]!=IMAGE_COLOR) { // 1) 배경 혹은 2) 이미 카운팅된 셀
            return 0;
        }
        else {
            grid[x][y] = ALREADY_COUNTED;
            return 1+countCells(x-1,y-1)+countCells(x-1,y)+countCells(x+1,y-1)+countCells(x,y-1)+
                    countCells(x,y+1)+countCells(x+1,y-1)+countCells(x+1,y)+countCells(x+1,y+1);
        }
    }
}

이전 포스팅에서 다뤘던 미로 찾기와 유사하게, countCells 함수에서 우선적으로

1) 입력 받은 좌표 x, y가 주어진 grid의 크기를 벗어나지 않는지 확인하는 유효성 검증을 하고 

2) gird[x][y]가 IMAGE_COLOR가 아닌 경우, 즉 BACKGROUND_COLOR이거나 아니면 이전에 다른 countCells 함수에 의해 이미 카운팅 된 셀인 경우에도 역시 0을 return 하고

3) 1번과 2번이 아닌 경우에만 해당 셀을 카운팅 된 셀로 변경하여 다른 셀에서 넘어온 countCells 함수에 의해 중복 카운팅 되는 걸 막고, return으로 1과 함께 해당 셀을 둘러싼 8개의 셀들에 대해서도 countCells 함수를 재귀 호출해줍니다.