Recursion 응용(2)

Counting cells in a Blob 문제

조건

- Binary 이미지

- 각 픽셀은 background pixel이거나 image pixel이다.

- 서로 연결된 image pixel의 집합을 blob이라 칭한다.

- 상하좌우뿐 아리라 대각으로 연결된것도 같은 집합이라 간주한다.

- 인접한 8개 픽셀에 대해서 북, 북동, 동,... 순서의 시계방향으로 탐색한다.

- 입력

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

하나의 좌표 (x, y)

- 출력

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

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

순환적으로 생각해보기

- 현재 픽셀이 속한 blob의 크기를 카운트하려면

현재 픽셀이 image color가 아니라면

0을 반환한다.

현재 픽셀이 image color라면

현재 픽셀을 우선 카운트한다 (count = 1)

현재 픽셀이 중복 카운트되는 것을 방지하기 위해 다른 색으로 칠한다.

현재 픽셀에 이웃한 모든 픽셀들에 대해서 (총 8개의 픽셀)

해당 픽셀이 속한 blob의 크기를 세서 카운트에 더해준다.

카운터를 반환한다.

슈도 코드

Algorithm for countCells (x, y)

if the pixel (x, y) is outside the grid

the result is 0;

else if pixel (x, y) is not an image pixel (black) or already counted (red)

the result is 0;

else

set the color of the pixel (x, y) to a red color

the result is 1 plus the number of cells in each piece of the blob that includes a nearest neighbor;

구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class CountingCellsInABlob {
    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 int N = 8;
    private static int BACKGROUND_COLOR = 0;
    private static int IMAGE_COLOR = 1;
    private static int ALREADY_COUNTED_COLOR = 2;
    
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write("Blob을 찾고자 하는 좌표를 입력해주세요 : ");
        bw.flush();
        
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        
        bw.write("입력된 좌표가 포함된 Blob의 총 개수는 " + String.valueOf(countCells(x, y)) + "개 입니다.");
        bw.flush();
        bw.close();
    }
    
    public static int countCells (int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N)
            return 0;
        else if (grid[x][y] != IMAGE_COLOR)
            return 0;
        else {
            grid[x][y] = ALREADY_COUNTED_COLOR;
            //북쪽부터 시작하여 시계방향으로 순환함수를 통해 Blob들의 카운트를 센다.
            return 1 + countCells(x - 1, y) + countCells(x - 1, y + 1)
            + countCells(x, y + 1) + countCells(x + 1, y + 1)
            + countCells(x + 1, y) + countCells(x + 1, y - 1)
            + countCells(x, y - 1) + countCells(x - 1, y - 1);
        }
    }
}