[오늘의 키워드]

프로그래머스 - 쿼드압축 후 개수 세기 (Lv.2)

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

문제 설명

쿼드트리 문제이다.
0과 1로 이루어진 정사각형 배열 데이터를 쿼드트리로 압축한 뒤, 0과 1의 총 개수를 return하면 된다.

쿼드트리로 압축하는 방법은 입출력 예를 보면 한 번에 이해할 수 있다.

입출력 예

2차원 배열을 한 구역 안에 모든 데이터가 같은 값을 가질 때까지 4등분한다.

코드

public class Solution
{
    public void DFS(int x, int y, int size, int[,] arr, int[] answer)
    {
        bool flag = true;
        for (int i = x; i < x + size; i++)
        {
            for (int j = y; j < y + size; j++)
            {
                if (arr[i, j] != arr[x, y])
                {
                    flag = false;
                    break;
                }
            }
        }

        if (flag)
        {
            answer[arr[x, y]]++;
            return;
        }

        size /= 2;
        DFS(x, y, size, arr, answer);
        DFS(x + size, y, size, arr, answer);
        DFS(x, y + size, size, arr, answer);
        DFS(x + size, y + size, size, arr, answer);
    }

    public int[] solution(int[,] arr)
    {
        int[] answer = new int[] { 0, 0 };
        DFS(0, 0, arr.GetLength(0), arr, answer);
        return answer;
    }
}

DFS를 이용했다.
재귀함수의 내용을 간략하게 설명해보자면 ..

1. 현재 구역 내의 모든 데이터가 같은 값인지 판단한다.
2. 모두 같다면 현재 구역의 데이터 (0 or 1)의 개수를 1 늘리고 분할을 종료한다.
3. 아니라면 현재 구역을 4분할하여 다시 탐색한다.