[C#] 쿼드압축후 개수 세기(재귀)

프로그래머스 문제

문제 설명

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

---

입출력 예

arrresult

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

 

내 풀이

using System;
 
public class Solution {
    int[,] temp;
    int[] answer = new int[]{0,0};
    public int[] solution(int[,] arr) {
        temp=arr;
        JaeGui(0,0,arr.GetLength(0));
        return answer;
    }
    
    public void JaeGui(int startx,int starty,int sideLength)
    {   
        bool AllZero=true;
        bool AllOne=true;
        for (int i = startx; i < startx + sideLength; i++)
        {
            for (int j = starty; j < starty + sideLength; j++)
            {
                if (temp[i,j] == 0)
                {
                    AllOne = false;
                }
                if (temp[i,j] == 1)
                {
                    AllZero = false;
                }
            }
        }
        if (AllZero == true)
        {
            answer[0]++;
            return;
        }
        if (AllOne == true)
        {
            answer[1]++;
            return;
        }
        JaeGui(startx, starty, sideLength / 2);
        JaeGui(startx, starty + sideLength / 2, sideLength / 2);
        JaeGui(startx + sideLength / 2, starty, sideLength / 2);
        JaeGui(startx + sideLength / 2, starty + sideLength / 2, sideLength / 2);
    }
}

느낀점: 우선 재귀로 문제를 처음 해결해봐서 상당히 낯선 문제였다.

문제의 핵심은 큰 사각형을 4분할 하는것인데 0 or 1 로 쿼드 압축이 되는 경우에는 압축을 한 후 다시 분할을 진행하는 것이다.

즉 특수 조건에는 return 해준 후 재귀과정을 반복하는 것이다.

많은 시행착오 끝에 정확한 조건을 찾아내었다.

 

1. 특정 범위가 모두 '0'인 경우

2. 특정 범위가 모두 '1'인 경우

3. 그게 아닌 경우

 

그 후 한 변의 길이를 나타내는 Size 변수가 1이 되면 리턴을 진행해준다.