[Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 순환 (Recursion) 의 응용 : Counting Cells in a Blob

Blob(이어진 블록) 세기

 

 

문제

 

그리드에서 흰색 부분은 backgroud pixel, 파란색 부분은 image pixel이며

image pixel이 서로 이어지게 연결된 집합을 blob이라고 한다. (상하좌우, 대각방향도 이어진 것으로 간주)

 

 

해당 예제에서는 위처럼 4개의 blob이 존재하고, 한 blob 안의 image pixel의 개수가 size(크기)가 된다.

 

 

 

알고리즘

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

입력

N*N 크기의 2차원 그리드

하나의 좌표(x,y)

 

출력

픽셀 (x,y)가 포함된 blob의 크기

(x,y)가 어떤 blob에도 속하지 않는 경우 0

 

 

 

sudo code

 

 1) 그리드를 벗어나거나 2) image pixel이 아니거나 이미 방문한 적이 있는 pixel 이라면 false를 반환해 불필요한 곳을 탐색하지 못하도록 한다. 

 

 

1) 2)에 해당하지 않는다면, 그 픽셀을 포함한 blob을 찾는다.

픽셀을 탐색할 때 위 알고리즘처럼 빨간색으로 "이 셀은 방문했다!!"고 표시해두고, 근접 픽셀 중 해당 픽셀과 이어지는 픽셀이 있는지 확인하는 동작을 반복한다.

 

 

 

int result 변수를 왜 선언하셨는지 모르겠다 필요없다. result += 1; 을 한 후 return result;가 아니라 return 문에서 직접적으로 정수 값을 반환해주고 있기 때문이다.

 

 

if문은 1)의 경우를 else if문은 2)의 경우로, 그리드를 벗어나거나 backgroud pixel인 곳은 탐색하지 않도록 만들어주고

else 문에서 image pixel일 경우 이미 방문했다고 표시해준 후 근접한 8개의 픽셀들을 탐색한다.

이 과정에서 countCells함수가 재호출(순환)되며, 근접한 픽셀의 근접한 픽셀들까지 모두 체크한 후 blob의 결과를 얻을 수 있다.

 

 

 

 

 

코드

import java.util.Scanner;

public class example {
    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}
    };

    private static final int BACKGOUND_COLOR = 0;
    private static final int IMAGE_COLOUR = 1;
    private static final int ALREADY_COUNTED = 2;

    public static int countCells(int x, int y) {
        if(x<0 || y<0 || x>=N || y>=N) return 0; // 그리드를 벗어난 경우
        else if(grid[x][y] != IMAGE_COLOUR) return 0; // backgroud pixel이거나 이미 개수를 센 pixel일 경우
        else {
            grid[x][y] = ALREADY_COUNTED;
            return 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);
            // 북, 북동, 동, 동남, ... 시계 방향으로 근접 픽셀에서 해당 픽셀과 이어지는지 탐색
        }
    }


    public static void main(String[] args) {
        System.out.println(countCells(5,3));
    }
}

 

결과