Recursion - Blob 셀 카운트

2021/03/01 - [개발/알고리즘 기초공부] - Recursion - 순환함수(재귀함수) (1)

2021/03/01 - [개발/알고리즘 기초공부] - Recursion - 순환함수(재귀함수) (2)

2021/03/02 - [개발/알고리즘 기초공부] - Recursion - 순환함수(재귀함수) (3)

2021/03/02 - [개발/알고리즘 기초공부] - Recursion - 미로찾기

 

입력으로 Binary 이미지가 주어진다.

각 픽셀은 background pixel(흰색)이거나 혹은 imagepixel(파란색)이다.

서로 연결된 image pixel들의 집합을 Blob이라고 부른다.

상하좌우 및 대각방향으로도 연결된 것을 Blob으로 간주한다. 

다음의 그림처럼 각각 사이즈가 5, 1, 13, 5 인 네개의 Blob가 있을때, 

주어진 좌표 (x, y)가 속한 Blob의 사이즈를 반환

    

 

public class CountCellBlob {
    
    public static void main(String[] args) throws Exception {
        
        //입력
        // N*N 크기의 2차원 그리드
        // 하나의 좌표 (x,y)

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

        //1. 좌표 (x,y)가 0이면 0 리턴하고 false
        //2. 좌표 (x,y)가 1이면 1을 add 하고 true
        private static int[][] map {
            {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 final int CHECKED = 2;

        public static int countCell(int x, int y){
            int cnt = 0;
            if (x < 0 || y < 0 || x >= N || y>= N) return 0;
            else if (map[x][y] != 1 ) return 0;
            else {
                cnt++;
                map[x][y] = 2;
                cnt = countCell(x-1, y-1)+ countCell(x, y-1)+ countCell(x+1, y);
                cnt = countCell(x-1, y)+ countCell(x+1, y);
                cnt = countCell(x-1, y+1)+ countCell(x, y+1)+ countCell(x+1, y+1);
            }
            return cnt;
        }
        
    }
}