[Java][프로그래머스] 68936번, 쿼드압축 후 개수 세기

 

프로그래머스

 

68936, 쿼드압축 후 개수 세기

🔥 난이도 : LEVEL 2

 

📁 프로세스

 

[문제 설명]

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

 

🔽문제풀이

Quadtree - Wikipedia

이번 문제는 쿼드트리에 관한 문제이다. (0,0) 좌표에서 주어진 배열의 길이를 기준으로 재귀를 호출하며 압축이 가능한지여부를 판단한다.

 

public void quad(int[][] arr, int x, int y, int size){
    if(zip(arr,x,y,size, arr[x][y])){
        if(arr[x][y] == 1)
            answer[1]++;
        else answer[0]++;
        return ;
    }

    // 4분할 quad 재귀
    quad(arr,x,y, size/2);
    quad(arr,x,y + size/2, size/2);
    quad(arr,x+size/2,y, size/2);
    quad(arr,x+size/2,y + size/2, size/2);
}

..
..

public boolean zip(int[][] arr, int x, int y, int size, int val) {
    for(int i = x; i < x + size; i++) {
        for(int j = y; j < y + size; j++) {
            if(arr[i][j] != val)
                return false;
        }
    }

    return true;
}

 

위의 코드를 보면 주어진 x,y 좌표에서 길이 size 까지 모든 좌표를 탐색한다. 탐색하며 주어진 좌표의 값과 다른 값이 하나라도 존재한다면 이는 압축할 수 없음을 의미한다(zip). 즉, 압축할 수 있다면 주어진 좌표의 값이 0인지 1인지를 판단하고 answer 에 개수를 더해준다는 의미이다.

 

정리하자면

if(zip(arr,x,y,size, arr[x][y])){
    if(arr[x][y] == 1)
        answer[1]++;
    else answer[0]++;
    return ;
}

 

1. 주어진 좌표에서 해당 길이만큼을 압축할 수 있다.

- 더 이상 분할하지 않고 x ~ x+size, y+ y+size 의 값에 해당하는(0 또는 1) 값을 1 더해준다.

 

 

// 4분할 quad 재귀
quad(arr,x,y, size/2);
quad(arr,x,y + size/2, size/2);
quad(arr,x+size/2,y, size/2);
quad(arr,x+size/2,y + size/2, size/2);

 

2. 주어진 좌표에서 해당 길이만큼을 압축할 수 없다.

- 4분할 재귀를 통해 모든 범위를 탐색한다.

 

✅전체코드

class Solution {
    static int[] answer;
    
    public int[] solution(int[][] arr) {
        answer = new int[2];
        quad(arr,0,0,arr.length);
        return answer;
    }
    
     public boolean zip(int[][] arr, int x, int y, int size, int val) {
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                if(arr[i][j] != val)
                    return false;
            }
        }

        return true;
    }

    public void quad(int[][] arr, int x, int y, int size){
        if(zip(arr,x,y,size, arr[x][y])){
            if(arr[x][y] == 1)
                answer[1]++;
            else answer[0]++;
            return ;
        }

        // 4분할 quad 재귀
        quad(arr,x,y, size/2);
        quad(arr,x,y + size/2, size/2);
        quad(arr,x+size/2,y, size/2);
        quad(arr,x+size/2,y + size/2, size/2);
    }
}

 

재귀를 사용하는 알고리즘 파트에 많이 미약한 것 같다. 항상 로직을 설계할 때 매개변수와 얼마나 재귀할 지에 대한 충분한 고려하는 연습이 필요한 것 같다 😭