[프로그래머스 C#] Lv.2 쿼드압축 후 개수 세기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따라 쿼드압축을 진행했을 때, 남아있는 0과 1의 개수를 반환하는 문제

- 각 영역에 대한 연산을 하는 메서드를 재귀호출하여 풀이함

- 영역 안의 값이 모두 같은 숫자로 이루어졌다면 쿼드압축하고 카운팅 (이후 연산하지 않음)

- 영역 안의 값이 모두 같은 숫자로 이루어지지 않았다면 무조건 4등분하여 다시 체크하면 됨

 

4등분한 각각의 영역을 재귀호출하기 위한 방법

무조건 4등분하기 떄문에 명확한 기준을 놓을 수 있음

- 4등분된 영역의 한 변의 길이는 4등분하기 전의 길이의 절반

- 왼쪽위 끝 인덱스 좌표부터 탐색해야하는 길이만큼 탐색해 원하는 영역만 탐색

ex) 8x8 범위를 탐색한다면 인덱스를 기준으로 a를 0~3, b를 4~7 영역이라고 했을 때,

arr[a, a], arr[b, a], arr[a, b], arr[b, b] 영역으로 나누어 다시 체크

 

재귀함수인 메서드 Function의 매개변수 설명

- posY : 탐색 대상 영역의 왼쪽위 끝의 인덱스 Y 좌표

- posX : 탐색 대상 영역의 왼쪽위 끝의 인덱스 X 좌표

- length : 탐색 대상 정사각형 영역의 한 변의 길이

 

주석 참조

    using System;

    public class Solution
    {
        public int[] solution(int[,] arr)
        {
            int[] answer = new int[2] { 0, 0 }; // 0 : zeroCount, 1 : oneCount

            Function(0, 0, arr.GetLength(0), arr, ref answer);

            return answer;
        }

        public void Function(int posY, int posX, int length, int[,] arr, ref int[] answer)
        {
            int num = arr[posY, posX]; // 비교 기준

            // 압축할 수 없는 크기라면 카운팅
            if (length == 1)
            {
                answer[num]++;
                return;
            }

            // 범위 내의 영역이 같은 숫자로만 이루어져 있는지 확인
            bool isCheck = true;
            for (int y = posY; y < posY + length; y++)
            {
                for (int x = posX; x < posX + length; x++)
                {
                    // 같은 숫자로만 이루어지지 않았을 때
                    if (arr[y, x] != num)
                    {
                        isCheck = false;
                        break;
                    }
                }
            }

            // 같은 숫자로만 이루어져 있다면 쿼드압축하고 카운팅
            if (isCheck)
            {
                answer[num]++;
                return;
            }

            // 4개의 영역에 대하여 재귀호출
            int halfLength = length / 2;
            Function(posY, posX, halfLength, arr, ref answer); // LeftUp
            Function(posY + halfLength, posX, halfLength, arr, ref answer); // LeftDown
            Function(posY, posX + halfLength, halfLength, arr, ref answer); // RightUp
            Function(posY + halfLength, posX + halfLength, halfLength, arr, ref answer); // RightDown
        }
    }