[Algorithm] - Counting Cells BLOB - Recursion

blob 알고리즘 특징은 인접한 셀을 찾아서 사이즈를 구하는 것이다.

여기서 인접한의 조건은 다양할수 있지만, 내가 푼 문제는 [상하좌우 + 대각선] 까지 총 8방향으로 가정했다.

재귀함수로 구현했으며 기본으로 배우고 문제를 쫌 다른각도로 변형시켜서 풀었다.

문제 - 이미지 개수를 구하고, 이미지중에서 가장큰 사이즈를 구하기


package recursive;

public class CountCells {
static int[][] blob = {
{0,0,0,0,0,0,1},
{0,1,1,1,0,1,1},
{0,1,0,1,0,0,0},
{0,0,0,0,0,0,0},
{0,1,1,0,1,1,0},
{0,0,1,0,0,0,0},
{0,0,1,0,0,0,0},
};
private static final int BACKGROUND_COLOR = 0; //배
private static final int IMAGE_COLOR      = 1; //이미지
private static final int CHANGE_COLOR     = 2; //방문체크용
public static void main(String[] args){
//image개수를 구하면서 가장큰 사이즈 찾기
int maxSize = 0;
int imageCnt = 0;
for(int i=0; i<7; i++){
for(int j=0; j<7; j++){
//이미 카운팅한 이미지면 패스
if(blob[i][j] != CHANGE_COLOR && blob[i][j] != BACKGROUND_COLOR) {
imageCnt++; //배경이 아니고 이미 카운팅한 칼라가 아닌 이미지칼라를 만나는 경우.
int imageSize = getImageSize(i,j);
if(maxSize < imageSize) maxSize = imageSize;
}
}
}
System.out.println(imageCnt + " " +maxSize);
}
static int getImageSize(int x, int y){
//1.주어진 배열외의 값은 0
if(x<0 || y<0 || x>=7 || y>=7) return 0;
//2.이미지값(1)이 아니면 0
else if(blob[x][y] != IMAGE_COLOR) return 0;
else{
//3.이미지색을 변경하면서 중복카운팅 방지
blob[x][y] = CHANGE_COLOR;
//4.인접한 이미지를 찾아서 사이즈를 계속 합쳐준다.
return 1 + getImageSize(x-1,y) + getImageSize(x-1,y-1) + getImageSize(x,y-1) +
getImageSize(x+1,y-1) + getImageSize(x+1,y) + getImageSize(x+1,y+1) +
getImageSize(x-1,y+1) + getImageSize(x,y+1);
}
}
}

댓글