[알고리즘] Recursion의 응용 - Counting Cells in a Blob

인프런 무료 강의 권오흠교수님 '영리한 프로그래밍을 위한 알고리즘 강좌' 보면서 공부한 내용입니다.
부족한 내용이나 잘못된 내용은 댓글남겨주시면 감사하겠습니다!

출처 : https://inf.run/iezc

이번에는 순환함수를 응용하여 Counting Cells in a Blob를 해보았다.

 

Blob : 서로 연결된 image pixel들의 집합

각 픽셀은 background pixel이거나 혹은 image pixel
상하좌우 및 대각방향으로도 연결된 것으로 간주

입력 :
- N * N 크기의 2차원 그리드
- 하나의 좌표 (x, y)

출력 :
- 픽셀 (x,y)가 포함된 blob의 크기,
- (x,y)가 어떤 blob에도 속하지 않는 경우에는 0

현재 픽셀이 이 속한 blob의 크기를 카운트하려면
현재 픽셀이 image color가 아니라면 0을 반환
현재 픽셀이 image color라면 
먼저 현재 픽셀을 카운트 (count = 1)
현재 픽셀이 중복 카운트되는 것을 방지하기 위해 다른색으로 칠함
현재 픽셀이 이웃한 모든 픽셀들에 대해서
그 픽셀이 속한 blob의 크기를 카운트하여 카운트에 더해줌

카운터를 반환

 

// 입력으로 하나의 x,y 좌표를 받음
	 Algorithm for countCells(x, y)
	 
	 // 픽셀이 유효한 값이 아닐 경우 ex) x<0. y<0. x>N, y<N
	 if the pixel (x, y) is outside the grid
	 	the result is 0;
	 
	 // x, y가 이미지 픽셀이 아니거나, 이미 카운트 된 픽셀일 경우
	 else if pixel (x, y) is not an image pixel or already counted
	 	the result is 0;
	 	
	 // 이미지 픽셀 + 이미 카운트 된 픽셀 X
	 else
	 	// 카운트를 하기 위해 빨간색으로 칠하고
	 	set the colour of the pixel (x, y) to a red colour; // 이미 카운트 되었음을 표시
	 	// 카운트 + 1, 인접한 4개 픽셀에 대해서도 진행 
	 	the result is 1 plus the number of cells in each piece of
	 		the blob that includes a nearest neighbour;

 

/*
 * Recursion의 응용 - Counting Cells in a Blob 5-02
 * -> 18
 */
package edu.recursion;

public class Recursion05_02 {
	private static int N = 8;
	
	private static int [][] grid ={
			{1, 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}
	};
	
	private static final int BACKGROUND_COLOR = 0; 
	private static final int IMAGE_COLOR = 1; 
	private static final int ALREADY_COUNT = 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_COLOR)
			return 0; 
		
		
		else {
			grid[x][y] = ALREADY_COUNT;
			
			// 인접한 8개의 좌표
			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) {
		int result = countCells(0, 0); 
		System.out.println(result);
	}
}