Recursion 응용 2 - 블롭 카운팅

• 해당 게시물은 인프런 - "영리한 프로그래밍을 위한 알고리즘 강좌" 강의를 참고하여 작성한 글 입니다
• 강의 링크

문제

그림에서 특정 좌표의 blob의 크기를 구하는 문제다

• Binary 이미지다
• 각 픽셀은 image pixel 또는 background pixel이다
• 서로 연결된 image pixel들을 blob이라고 부른다
• 상하좌우 및 대각 방향으로도 연결된 것으로 간주한다

위 그림에서는 총 4개의 blob이 있다

문제를 정의하면 다음과 같다

• 입력:
  • N x N 크기의 2차원 그리드
  • 하나의 좌표 (x, y)
• 출력:
  • 픽셀 (x, y)가 포함된 blob의 크기
  • (x, y)가 어떤 blob에도 속하지 않는 경우에는 0

Recursive Thinking

이 문제를 Recursion을 이용해 해결해 본다

수도 코드는 다음과 같다

현재 픽셀이 image color가 아니라면
    0을 반환
현재 픽셀이 image color라면
    현재 픽셀을 카운트한다 (count = 1)
    현재 픽셀을 다른 색으로 칠한다 (중복 카운트 방지)
    현재 픽셀과 이웃한(상하좌우, 대각선) 모든 픽셀들에 대해서
        그 픽셀이 속한 blob의 크기를 계산하여 count에 더한다
    count 반환

순환적 알고리즘

시작점은 (5, 3)이라고 가정, 즉 이 픽셀이 포함된 blob의 크기를 계산한다

현재 count = 0이다

현재 픽셀을 다른 색으로 칠하고 count를 1 증가한다

다른 색으로 칠하면 픽셀이 중복 count 되는 것을 방지한다

현재 count = 1이다

인접한 8개 픽셀에 대해서 순서대로 그 픽셀이 포함된 blob 크기를 구한다

순서는 북 -> 북동 -> 동 -> 동남 -> 남 -> 남서 -> 서 -> 북서 순서다

북쪽 픽셀이 포함된 blob의 크기는 0이다

count 값은 변함 없이 1이다

북동쪽 픽셀이 속한 blob을 count하고, count된 픽셀들을 색칠한다

3개의 픽셀이 북동쪽 픽셀의 속한 blob이다

count 값은 1 + 3 = 4다

동쪽과 남동쪽 픽셀이 포함된 blob 크기는 0이다

count 값은 변함없이 4다

남쪽 픽셀이 속한 blob을 카운트 한다

남쪽 픽셀이 속한 blob 크기는 9다

현재 count 값은 4 + 9 = 13이다

남서, 서 방향의 픽셀이 속한 blob은 없다

북서 방향의 픽셀은 이미 계산되었다

모든 방향 검사가 끝났다

현재 count 값은 변함없이 13이다

Counting Cells in a Blob

알고리즘은 다음과 같다

if the pixel (x, y) is outside the grid
  the result is 0;
else if pixel (x, y) is not an image pixel or already counted
  the result is 0;
else
  set the color of the pixel (x, y) to a red color; // 이미 count 됨 표시
  the result is 1 plus the number of cells in each piece of 
    the blob that includes a nearest neighbor;

자바 코드

자바로 만든 코드는 다음과 같다

public class CountingCells {

    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 = {
            {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},
    };

    public int countCells(int x, int y) {
        int result = 0;

        if (x < 0 || x >= N || y < 0 || y >= N) {
            result = 0;
        } else if (grid[x][y] != IMAGE_COLOR) {
            result = 0;
        } else {
            grid[x][y] = ALREADY_COUNTED;
            result = 1 +
                    countCells(x - 1, y + 1) +
                    countCells(x, y + 1) +
                    countCells(x + 1, y + 1) +
                    countCells(x - 1, y) +
                    countCells(x + 1, y) +
                    countCells(x - 1, y - 1) +
                    countCells(x, y - 1) +
                    countCells(x + 1, y - 1);
        }

        return result;
    }

    public static void main(String[] args) {
        int count = new CountingCells().countCells(5, 3);
        System.out.println("count = " + count);
    }
}

코드

https://github.com/yanJuicy/algorithm-for-clever-programming