알고리즘 - Blob 크기 구하기(재귀)

특점 지점에서 시작해서 연결되어있는 Blob의 크기가 얼마인지 구하는 메서드 이다.

문제를 작게 쪼개어서 보는것이 중요하다.

public class CountCells {
    public static void main(String[] args) {
        System.out.println(countCells(1, 1));
    }
    // 결과값은 17

    private static int N = 8;
    private static int[][] grid = {
            {0, 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 int BACKGRUND_COLOR = 0;
    private static int IMAGE_COLOR = 1; // 색 칠해져있으면 1
    private static int ALREADY_COUNTED = 2; // 이미 카운트 되었으면 2


    public static int countCells(int x, int y) {
        int result;
        if (x < 0 || y < 0 || x >= N || y >= N) return 0;
        else if (grid[x][y] != IMAGE_COLOR) return 0; // 색상 없으면 count안하고 0 리턴
        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);
            // 상하좌우, 각 대각선에서도 연결된곳 있는지 계산해서 더해주기
        }
    }
}