프로그래머스 lv2 쿼드압축 후 개수 세기

문제링크

쿼드압축 후 개수 세기

문제 풀이

Top-Down으로 생각해보면 풀리는 문제이다.

1. 주어진 2차원 배열이 모두 같은 수로 이루어져있는지 확인한다.
2. 맞다면 해당 2차원 배열의 첫번째 수에 해당되는 수를 카운트 + 1 해준다.
3. 아니라면 탐색하는 2차원 배열을 4등분하여 4등분되는 2차원 배열을 탐색할 수 있도록 한다. 그 뒤로는 1, 2, 3 의 반복이다. 이때 4등분 된 2차원 배열의 각 시작점은 (x, y) , (x + 2차원 배열 사이즈 / 2, y) , (x, y + 2차원 배열 사이즈 / 2), (x + 2차원 배열 사이즈 / 2, y + 2차원 배열 사이즈 / 2) 이다.

예를 들어 4 * 4 배열을 생각해보면, (0, 0), (0, 2), (2, 0), (2, 2)가 되는 것을 알 수 있다.

그리고 이거를 규칙을 구하면.. (여기서 len은 한 변의 길이다.)

이렇게 되는 것을 알 수 있다.

이것을 코드로 나타내보자.

class Solution {
    static int[] answer = new int[2];
    public int[] solution(int[][] arr){
        backTracking(arr, 0, 0, arr.length);
        return answer;
    }

    public void backTracking(int[][] arr, int x, int y, int quadSize){
        if(checkNum(arr, x, y, quadSize, arr[x][y])){
            if(arr[x][y] == 1){
                answer[1]++;
                return;
            }

            answer[0]++;
            return;
        }

		// 위에서 그렸던 정사각형을 4등분했을 때, 출발점에 맞춰서 탐색 시작
        backTracking(arr, x, y, quadSize/2);
        backTracking(arr, x + quadSize/2, y, quadSize/2);
        backTracking(arr, x, y + quadSize/2, quadSize/2);
        backTracking(arr, x + quadSize / 2, y + quadSize / 2, quadSize / 2);
    }

	// 주어진 2차원 배열 arr의 내부 구성값이 모두 같은가?
    public boolean checkNum(int [][] arr, int x, int y, int quadSize, int standard){
        // quadSize만큼만 정사각형 탐색
        for (int i = x; i < x + quadSize; i++) {
            for (int j = y; j < y + quadSize; j++) {
                if (arr[i][j] != standard) {
                    return false;
                }
            }
        }
        return true;
    }
}

소감

문제를 보고 아 이게 BFS, DFS, BackTracking 문제인 것을 바로 알아챌 수 있으려면 얼마나 풀어야하는걸까..

난 아직 잘 모르겠다