[알고리즘-자바] 프로그래머스 월간 코드 챌린지 시즌1 > 쿼드압축 후 개수 세기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68936?language=java 

프로그래머스

언어

자바 Java

로직

arr 배열은 정사각형 크기를 가지고 있습니다. 그렇기 때문에 배열의 크기를 절반으로 나누면 절반의 길이가 됩니다. 이것을 이용하여 문제에 접근할 수 있습니다.

 

전체 배열 탐색

전체 배열을 탐색하려면 어떻게 해야 할까요? 누구나 2중 for문을 이용해서 접근해야겠다라고 생각할 수 있습니다. 

그렇다면 가장 먼저 해야할 것은 (0, 0) 위치에서 배열의 끝까지 탐색을 해야 합니다. 왜냐하면 전체 배열에 담긴 숫자가 모두 같은 숫자인지 확인을 해야 하기 때문이죠.

배열 전체를 탐색하는 코드입니다. x와 y의 초기값으로 0이 저장되어 있습니다. (0, 0)부터 탐색을 시작하여 배열의 끝까지 탐색합니다. if문을 보면 arr [y][x] == arr [0][0]과 값이 증가하는 arr [i][j]를 비교하는 것을 알 수 있습니다. 해당 코드가 현재 구간 내에 같은 숫자로만 이루어져 있는지 확인하는 조건문입니다.

for (int i = y; i < y + length; i++) {
    for (int j = x; j < x + length; j++) {
        if (arr[y][x] != arr[i][j]) {
        // ..생략
        }
    }
}

구간 배열 탐색 1

전체 배열 탐색을 한 결과 중간에 다른 숫자가 있음을 알게 되었습니다. 그렇다면 구간을 4개로 나누어야 합니다. 배열의 경우 정사각형으로 이루어져 있기 때문에 배열 크기 / 2를 하여 절반의 길이를 구할 수 있습니다. 탐색 시작위치에서 가로로 절반, 세로로 절반 이동하면 총 4개의 구간으로 나뉘겠죠. 

위의 사진과 아래 코드를 봅시다. 

1. (x, y) == (0,0) -> 1번 점
2. (x + length, y) == (2,0) -> 2번점
3. (x, y + length) == (0,2) -> 3번점
4. (x + length, y + length) -> 4번점

if (arr[y][x] != arr[i][j]) {
    length /= 2;
    traverse(arr, x, y, length); //1
    traverse(arr, x + length, y, length); //2
    traverse(arr, x, y + length, length); //3
    traverse(arr, x + length, y + length, length); //4
    return;
}

구간 배열 탐색 2

구간 배열 탐색 1에서 탐색을 다시 진행합니다. 그 결과 구간 내에 숫자가 같지 않다면 또 다시 1번 과정을 반복해야 합니다. 이 때 재귀적으로 해야겠다고 생각할 수 있습니다. 

구간 배열 탐색1에서 사용한 코드를 반복문에 작성하면 재귀적으로 호출이 가능해집니다. 여기서 1~4번은 검은 상자, 노란 상자, 파란 상자 3개에 모두 적용됩니다.  

for (int i = y; i < y + length; i++) {
    for (int j = x; j < x + length; j++) {
        if (arr[y][x] != arr[i][j]) {
            length /= 2;
            traverse(arr, x, y, length); //1
            traverse(arr, x + length, y, length); //2
            traverse(arr, x, y + length, length); //3
            traverse(arr, x + length, y + length, length); //4
            return;
        }
    }
}

재귀 종료

재귀 함수를 종료하는 코드는 어떻게 작성하면 될까요? 사실 종료 코드가 따로 필요하지 않습니다. traverse 메서드에 좌표와 길이를 넘겨주는데 이것들이 for문을 돌리는데 적합한지 알아서 걸러지기 때문입니다.

그렇다면 return문의 역할이 무엇일까요? 문제에서 4개의 구간으로 나누라고 했습니다. 즉 1~4번으로 구간을 나누어서 재귀함수를 호출하였기 때문에 더 이상 해당 메서드(반복문)를 실행시킬 필요가 없습니다.

---

코드

class Solution {
    private int zero, one;
    public int[] solution(int[][] arr) {

        traverse(arr, 0, 0, arr.length);

        return new int[]{zero, one};
    }

    private void traverse(int[][] arr, int x, int y, int length) {
        for (int i = y; i < y + length; i++) {
            for (int j = x; j < x + length; j++) {
                if (arr[y][x] != arr[i][j]) {
                    length /= 2;
                    traverse(arr, x, y, length);
                    traverse(arr, x + length, y, length);
                    traverse(arr, x, y + length, length);
                    traverse(arr, x + length, y + length, length);
                    return;
                }
            }
        }

        if (arr[y][x] == 0)
            zero++;
        else
            one++;
    }
}