재귀함수 공부...(feat. Counting Cells in a Blob)

문제는

https://www.youtube.com/watch?v=HHJFlVT1tBw 

요기에 있다.

 

이번에는 그냥 문제만 보고 풀어봤다.

 

이전 미로문제처럼 비슷하게 풀면되겠거니 생각해서 처음 코드를 짰을 때는 뭔가 base 부분이 이상했다.

어떻게 코드를 시작했냐면 아래와 같이 시작했다.

  public static boolean recur(int[][] board, int x, int y, boolean prev) {
            if (x < 0 || x >= board.length || y < 0 || y >= board.length || board[y][x] == 1) {
                return false;
            } else if (board[y][x] == 0) {
            	...
            	return true;
            }
            .....
 }

이럴 경우 맨처음으로 주어진 좌표가 만약 색이 칠해져있는 좌표라면 바로 true를 리턴해버리면서 종료가 되어버려 주변으로 이동하면서 찾을 수가 없었다. 그래서 조금 고민해본 결과...

조건을 이전 좌표가 파란색일 경우에만 코드들을 실행되게 해버리면 된다. 그래서 재귀함수에다가 boolean 값을 추가로 받을 수 있게 해놓고 다시 코드를 짜봤다.

 

public class Test {
    public static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    public static int cnt = 0;

    public static void main(String[] args) {
        int[][] board = {{0, 1, 1, 1, 1, 1, 1, 0}, {1, 0, 0, 1, 1, 0, 1, 1}, {0, 0, 1, 1, 0, 1, 0, 1},
                {1, 1, 1, 1, 1, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1, 1},
                {0, 1, 1, 1, 0, 1, 1, 0}, {1, 0, 0, 1, 1, 0, 0, 0}};



        recur(board, 0, 2, true);


        System.out.println(cnt);
    }

    public static void recur(int[][] board, int x, int y, boolean prev) {
        if (prev) {
            if (x < 0 || x >= board.length || y < 0 || y >= board.length || board[y][x] == 1) {
                return;
            } else if (board[y][x] == 0) {
                cnt+=1;
                board[y][x] = 1;

                for (int[] direction : dir) {
                    recur(board, x + direction[0], y + direction[1], true);
                }
            }
        }
    }
}

 

그랬더니 잘돌아간다!

 메인 메소드에서 재귀함수 시작에 true를 준 이유는 어차피 처음으로 주어진 좌표는 이전좌표가 없지만 조건문을 돌려야 하기 때문에 그렇게 주었다. 메인메소드 자체에서 첫번째 좌표가 파란색인지 아닌지를 파악해서 넣는 것도 나쁘지는 않겠지만 굳이 그럴 필요가 없다고 생각했다. 어차피 저기 안 쪽에서 한번 검토해준다.

 

이번문제는 나름 잘풀어서 점점 실력이 늘고 있는 것 같아서 행복하다..