[Java] 쿼드압축 후 수 세기

programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

문제 설명

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

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

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

입출력 예

[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

---

import java.util.*;
class Solution {
    static int count;
    static int[] val = new int[2];
    public int[] solution(int[][] arr) {
        
        int size = arr.length;
        if(isAvail(arr, 0, 0, size)){
            int tmp = arr[0][0];
            val[tmp]++;
            return val;
        }
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                DFS(arr, size/2, i*(size/2), j*(size/2));   // 배열, 사이즈, 시작점
            }
        }
        int[] answer = val;
        return answer;
    }
   
    private static boolean isAvail(int[][] arr, int a, int b, int len){
        int tmp = arr[a][b];
        for(int i=a; i <a+len; i++){
            for(int j=b; j<b+len; j++){
                if(arr[i][j] != tmp) return false;
            }
        }
        return true;
    }
    private static void DFS(int[][] arr, int size, int x, int y){
        int tmp = arr[x][y];
        if(size == 1){
            val[tmp]++;
            return;
        }
        
        if(isAvail(arr, x, y, size)){
            val[tmp]++;
            return;
        }
        int len = size/2;
        DFS(arr, len, x, y);
        DFS(arr, len, x+len, y);
        DFS(arr, len, x, y+len);
        DFS(arr, len, x+len, y+len);
        
    }
}

내 풀이

 

백트래킹을 이용해서 문제를 해결했다.

 

처음에는 2차원 배열을 새로 생성하고 그 배열을 확인하는 방식으로 문제를 접근했으나 굳이 2차원 배열을 만들면서 메모리를 사용하는 것은 비효율적이라고 생각해서 인덱스를 접근하는 방식으로 진행했다.

 

먼저 size와 좌표를 파라미터로 전달해서 다음 조건을 검사하였다.

 

1. size가 1인가? => 더 이상 쪼갤 수 없기 때문에 그냥 그 값을 1 증가시킨다.

2. 압축이 가능한가? => isAvail() 메소드로 이를 확인하였다.

 

만약 위의 두 조건에 해당되지 않는다면 더 쪼개서 나눠 들어가야 하기 때문에 마지막 DFS 4개의 문장처럼 size를 반으로 줄이고, 인덱스를 4부분으로 나눠서 탐색하였다.