AlgorithmProgrammers

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

1. 쿼드압축 후 개수 세기

1.1. 컴퓨팅적 사고

  1. 가장왼쪽위의 좌표를 기준으로 현재 탐색하고자 하는 정사각형의 한변의 길이를 통해서 탐색합니다. 가장 왼쪽지점을 기준으로 처리합니다. 분할 후도 같게 생각합니다.
  2. 3가지 경우의수: 특정 범위가 모두 '0’인 경우, 특정 범위가 모두 ‘1’ 인경우, 그게 아닌경우를 찾아냅니다.
    이것들을 DFS로 처리하여 (x,y),(x+size,y), (x,y+size),(x+size,y+size) 총 네가지경우로 나누어서 생각을 합니다.
  3. 값을 절반씩 나누어가면서 처리하면서 진행합니다.

1 0 0 0
0 1 0 0
1 1 1 0
1 1 0 0

테스트케이스로 다음과 같이 주어졌다고 가정하겠습니다.

1번 사각형 왼쪽 상단: (x , y) , SIZE / 2
2번 사각형 오른쪽 상단: (x , y + SIZE / 2) , SIZE / 2
3번 사각형 왼쪽 하단: (x + K / 2 , y) , SIZE / 2
4번 사각형 오른쪽 하단: (x + K / 2 , y + SIZE / 2) , SIZE / 2
의 경우로 나타낼 수 있습니다.

1.2. 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 가장왼쪽위의 좌표를 기준으로 현재 탐색하고자 하는 정사각형의 한변의 길이를 통해서 탐색
// 3가지 경우의수: 특정 범위가 모두 '0'인 경우, 특정 범위가 모두 '1' 인경우, 그게 아닌경우

public class 쿼드압축후개수세기 {
    static int[] answer;
    public static void main(String[] args) {
        solution(new int[][]{{1,1,0,0},{1,0,0,0},{1,0,0,1},{1,1,1,1}});
    }
    static int[] solution(int[][] arr) {
        answer = new int[2];
        dfs(0,0,arr.length,arr);
        for (int i : answer) {
            System.out.println("i = " + i);
        }
        return answer;
    }

    // 현재 범위의 가장 왼쪽 위의 좌표, 현재 범위의 정사각형의 한 변의 길이

    static void dfs(int x, int y, int squareSize, int[][] arr) {
        boolean isOneCheck = true;
        boolean isZeroCheck = true;
        for(int i=x; i<x+squareSize; i++){
            for(int j=y; j<y+squareSize; j++){
                if(arr[i][j] == 0) isOneCheck = false;
                if(arr[i][j] == 1) isZeroCheck = false;

            }
        }
        if(isZeroCheck){
            answer[0]++;
            return;
        }
        if(isOneCheck){
            answer[1]++;
            return;
        }
        dfs(x,y,squareSize/2, arr);
        dfs(x,y+squareSize/2,squareSize/2, arr);
        dfs(x+squareSize/2,y,squareSize/2, arr);
        dfs(x+squareSize/2,y+squareSize/2,squareSize/2, arr);
    }
}
Share