1-2. 재귀함수 - 픽셀수 구하기

1. 문제 설명

 출발 좌표를 임의로 지정했을 때, 인접한 셀이 몇개인지 세는 문제이다. 좌, 우, 상, 하, 대각선 위치에 셀이 0이 아니면 인접한 셀로 정의한다.

 백준 알고리즘의 Q2667 단지번호 붙이기와 비슷한 문제이다. 초록색 2번을 보면, 위쪽에 숫자가 있기 때문에 인접한 셀이다.

 하지만, 좌측와 우측에는 숫자가 없기 때문에 인접하다고 할 수 없다. 

2. Java구현

package recursive;

package codeSquad.recursive;

public class CountCellBlob {
    public static void main(String[] args) {
        int[][] image = {
                {1, 0, 0, 0, 0, 0, 0, 1},
                {0, 1, 1, 0, 0, 1, 0, 1},
                {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}
        };
        int x = 3;
        int y = 5;
        boolean[][] visted = new boolean[image.length][image[0].length];
        System.out.println(countBlob(x, y, image, visted));
    }

    public static int countBlob(int x, int y, int[][] image, boolean[][] visited) {
        int cnt = 0;
        if(x < 0 || x > image.length - 1 || y < 0 || y > image[0].length - 1) {
            return 0;
        } else if(visited[x][y] == true) {
            return 0;
        } else if (image[x][y] == 0) {
            visited[x][y] = true;
            return 0;
        } else {
            visited[x][y] = true;
            cnt = 1 + countBlob(x, y - 1, image, visited) + countBlob(x, y + 1, image, visited)
                    + countBlob(x - 1, y - 1, image, visited) + countBlob(x - 1, y, image, visited) + countBlob(x - 1, y + 1, image, visited)
                    + countBlob(x + 1, y - 1, image, visited) + countBlob(x + 1, y, image, visited) + countBlob(x + 1, y + 1, image, visited);
        }
        return cnt; 
    }
}

3. Pain Point

 

 처음에는 x와 y가 뒤바뀐 상태라서 좌우 이동이 조금 헷갈렸다. 이전에는 if문을 통해 조건을 확인하고 연산을 했는데, 이와 같이 연산을 해도 풀이가 가능하다.

 동작원리는 이전에 풀었던 백준 Q2667과 비슷해서 크게 시간은 오래 걸리지 않았다.. 다행히도.. 내 머리는 아직 쓰지 못할것은 아닌거 같다!