105. 쿼드압축 후 개수 세기

 

기본 틀 : 

 

using System;

public class Solution {
    public int[] solution(int[,] arr) {
        int[] answer = new int[] {};
        return answer;
    }
}

 

위의 문제는 2차원 배열을 4등분 후 각각 탐색을 진행하여 0과 1만 존재할 경우 개수를 증가 하면 되는 문제이다.

 

배열을 각 단계 별로 4등분 해야하기 때문에 재귀함수를 사용하면 편리하고

 

재귀함수의 매개변수로는 

 

    // 필요한 매개변수
    // 시작 x, y 위치
    // 배열 탐색 범위
    // 2차원 배열
    public void QuadCompression(int x, int y, int len, int[,] arr)

 

시작할 x, y 위치, 배열의 탐색 범위, 2차원 배열이 필요하다.

 

재귀 함수 내에서는 지정된 범위 내 값이 모두 0이나 1인지 확인 과정을 거쳐야 하기 때문에

 

        bool checkZero = true;
        bool checkOne = true;
        
        for(int i = x; i < x + len; i++)
        {
            for(int j = y; j < y + len; j++)
            {
                if(arr[i, j] == 0) checkOne = false;
                if(arr[i, j] == 1) checkZero = false;
            }
        }

 

위와 같이 반복문으로 배열 조회 및 bool 값으로 무슨 값이 존재하는지 체크해준다.

 

만약, 0이나 1만 해당 범위 내에 존재할 경우

    // 0과 1 결과 담을 그릇
    private int[] answer = new int[] {0,0};

        // 모든 값이 0 또는 1이면 개수 증가 및 재귀함수 종료
        if(checkZero) 
        {
            answer[0]++;
            return;
        }
        if(checkOne) 
        {
            answer[1]++;
            return;
        }

 

값을 증가시켜주고 return으로 재귀 함수를 종료시켜준다.

 

        // 원쪽 위 탐색
        QuadCompression(x, y, len / 2, arr);
        // 오른쪽 위 탐색
        QuadCompression(x + len / 2, y, len / 2, arr);
        // 윈쪽 아래 탐색
        QuadCompression(x, y + len / 2, len / 2, arr);
        // 오른쪽 아래 탐색
        QuadCompression(x + len / 2, y + len / 2, len / 2, arr);

 

그렇지 않은 경우 4 등분을 진행시켜주면 된다. 

 

그 결과, 다시 해당 함수가 지정된 범위 내에서 동작하게 되고 0이나 1만 가진 범위의 개수를 구할 수 있게 해준다.

 

전체 코드 : 

using System;

public class Solution {
    
    // 0과 1 결과 담을 그릇
    private int[] answer = new int[] {0,0};
    
    public int[] solution(int[,] arr) 
    {
        QuadCompression(0,0,arr.GetLength(0), arr);
        return answer;
    }
    
    // 필요한 매개변수
    // 시작 x, y 위치
    // 배열 탐색 범위
    // 2차원 배열
    public void QuadCompression(int x, int y, int len, int[,] arr)
    {
        bool checkZero = true;
        bool checkOne = true;
        
        for(int i = x; i < x + len; i++)
        {
            for(int j = y; j < y + len; j++)
            {
                if(arr[i, j] == 0) checkOne = false;
                if(arr[i, j] == 1) checkZero = false;
            }
        }
        
        // 모든 값이 0 또는 1이면 개수 증가 및 재귀함수 종료
        if(checkZero) 
        {
            answer[0]++;
            return;
        }
        if(checkOne) 
        {
            answer[1]++;
            return;
        }
        
        // 원쪽 위 탐색
        QuadCompression(x, y, len / 2, arr);
        // 오른쪽 위 탐색
        QuadCompression(x + len / 2, y, len / 2, arr);
        // 윈쪽 아래 탐색
        QuadCompression(x, y + len / 2, len / 2, arr);
        // 오른쪽 아래 탐색
        QuadCompression(x + len / 2, y + len / 2, len / 2, arr);
    }
}