[알고리즘] 쿼드 트리

 

이번에는 쿼드 트리의 작동 방식을 직접 알고리즘으로 제작하는 퀴즈를 풀어보았다.

여담으로 쿼드 트리는 데이터 베이스 검색 , 이미지 용량 최적화 , 지형 내에서 충돌 처리 등에서 사용가능한 방법으로 기본적으로 재귀적으로 분할하는 구조를 가진다.

---

 

 

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

프로그래머스

 

 

문제

 

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

---

나의 코드

public int[] solution(int[,] arr)
{
    int[] answer = new int[2] { 0,0 };
    int maxSplit = arr.GetLength(0) / 2;// 최대로 나눌 수 있는 횟수.
    List<int[,]> listarr = new List<int[,]>();// 4등분한 배열들을 저장할 배열.


    // 1. arr의 길이가 1이면 그대로 반환.
    if (maxSplit == 0)
    {
        if (arr[0,0] == 0)
        {
            answer = new int[] { 1,0 };
        }
        else if (arr[0,0] == 1)
        {
            answer = new int[] { 0,1 };
        }
        return answer;
    }

    // 2. arr의 길이가 2이상이면 4등분 재귀로 계산후 값을 반환.
    listarr = Split(arr, ref answer);// arr을 최대로 나누어 단일값 배열을 List로 반환.
    for (int i = 0; i < listarr.Count; i++)
    {
        if (listarr[i][0, 0] == 0)
        {
            answer[0]++;
        }
        else if (listarr[i][0, 0] == 1)
        {
            answer[1]++;
        }
    }

    return answer;
}

public List<int[,]> Split(int[,] arrS, ref int[] answer)//arrS의 2차원 배열의 GetLength(0) / 2 만큼 나누어 4등분한 배열들을 List로 반환 (List로 반환 해야 나머지 배열들을 한꺼번에 관리하기 쉬움)
{
    if (arrS.GetLength(0) == 1) // 더 이상 나눌 수 없으면 종료
    {
        return new List<int[,]>();
    }

    List<int[,]> listarr = SplitInFour(arrS, ref answer);

    // 분할된 배열들을 다시 재귀 호출하여 추가
    List<int[,]> newList = new List<int[,]>();
    foreach (var subArr in listarr)
    {
        newList.AddRange(Split(subArr, ref answer));
    }

    return newList;
}


// 2차원 배열을 4등분하는 메서드들
public List<int[,]> SplitInFour(int[,] original, ref int[] answer)
{
    int N = original.GetLength(0);
    int M = original.GetLength(1);
    int halfN = N / 2;
    int halfM = M / 2;

    List<int[,]> subMatrices = new List<int[,]>
    {
        GetSubMatrix(original, 0, 0, halfN, halfM),
        GetSubMatrix(original, 0, halfM, halfN, M),
        GetSubMatrix(original, halfN, 0, N, halfM),
        GetSubMatrix(original, halfN, halfM, N, M)
    };

    List<int> temp = new List<int> { 0, 0 };// 람다식에서는 ref를 사용할 수 없어 임시 변수 선언.
    // 동일한 값을 가진 배열 제거
    subMatrices = subMatrices.Where(item =>
    {
        if (item.Cast<int>().All(value => value == item[0, 0]))
        {
            temp[item[0,0]]++;
            return false; // 리스트에서 제거
        }
        return true;
    }).ToList();
    // temp의 값 answer에 더해줌.
    answer[0] += temp[0];
    answer[1] += temp[1];
    return subMatrices;
}
public int[,] GetSubMatrix(int[,] original, int startRow, int startCol, int endRow, int endCol)
{
    int rows = endRow - startRow;
    int cols = endCol - startCol;
    int[,] subMatrix = new int[rows, cols];

    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            subMatrix[i, j] = original[startRow + i, startCol + j];
        }
    }
    return subMatrix;
}

 

---

 

재귀 함수라는 점을 이용하면 훨씬 깔끔하게 구현할 방법이 있을 것 같은데, 아직은 알고리즘을 깔끔한 구조로 제작함에 있어서 어려움을 느끼고 있다. 아마도 Linq의 이해도 와 코드가 진행되는 방식이 아직 머릿속으로 잘 그려지지 않기 때문이라고 생각한다..

 

하지만, 말도안되는 난이도의 문제도 아니고 분명히 현업인들도 이러한 문제들을 어려움 없이 풀어낼 것이라고 생각하기 때문에 포기하지 않고 계속 풀이법과 접근법을 쌓아간다면, 언젠가는 눈에띄게 달라진 실력을 보여줄 수 있을것이라 생각한다.