[프로그래머스 Level.2] 쿼드압축 후 개수 세기 (월간 코드 챌린지 시즌1) (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

 

 

 

코딩테스트 연습 > 월간 코드 챌린지 시즌1 > 쿼드압축 후 개수 세기

 

 

문제 설명

 

 

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 입니다.

 

---

 

입출력 예

arr	result
[[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 해야 합니다.

 

 

 

나의 코드

class Solution {
    int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];
        
        dfs(0, 0, arr.length, arr);
            
        return answer;
    }
    
    public void dfs(int x, int y, int length, int[][] arr) {
        // 정사각형 내부 다 같은지 확인
        if(check(x, y, length, arr)) {
            answer[arr[x][y]]++;
            return;
        }
        
        // 내부 다르면 4개로 분할해서 재귀호출
        dfs(x, y, length/2, arr);
        dfs(x+length/2, y, length/2, arr);
        dfs(x, y+length/2, length/2, arr);
        dfs(x+length/2, y+length/2, length/2, arr);
    }

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

 

풀이

1. 완전탐색 dfs(깊이 우선 탐색)을 이용하여 푸는 문제이다.
2. 기준 좌표(정사각형의 맨 왼쪽 위) , 정사각형 한 변의 길이, arr 배열을 파라미터로 가지고 dfs를 진행하여 정사각형의 내부의 값이 전부 같지 않다면 한 변의 길이가 1일 때까지 계속 탐색해 나가는 방식이다.
3. arr 배열이 주어지면 기준 좌표(0,0)과 정사각형 한 변의 길이 arr.length와 배열 arr을 가지고 탐색을 시작한다.
4. 주어진 파라미터로 정사각형 내부가 같은지 확인하여 0으로 같다면 answer[0]을 증가시키고 1로 같다면 answer[1]을 증가시킨다.
5. 이중 for문을 통해 정사각형 내부의 값들을 확인 할 수 있다.
   (기준 y좌표 ~ 기준 y좌표 + length - 1), (기준 x좌표 ~ 기준 x좌표 + length - 1) 까지 배열의 값을 확인하여 값이 전부 같은지 확인하면 된다.
6. 정사각형 내부가 전부 같다면 answer를 증가시키고 종료하면 되지만 다르다면 다시 정사각형을 4등분해서 확인해야 한다.
7. 정사각형을 4등분하면 정사각형 한 변의 길이는 현재 길이의 반이 되므로 length/2가 되고 기준 좌표(정사각형의 맨 왼쪽 위)는 현재 (x, y)일 때 각각 (x, y), (x, y + length/2), (x + length/2, y), (x + length/2, y + length/2)가 된다.
8. 이렇게 하나의 정사각형의 내부가 다르면 4개의 정사각형으로 분할되므로 새로운 정사각형의 길이 length/2와 각각 기준좌표 4개를 가지고 4번 recursive 호출 해주어야 한다.
9. 정사각형의 내부 값이 계속 다르다면 계속 분할되다가 정사각형 한 변의 길이가 1일 때까지 확인하게 되어 하나의 값이므로 answer[해당값(0 or 1)]을 증가시키게 된다.