2025.3.28 알고리즘 코드카타

알고리즘 코드카타 - 105. 쿼드압축 후 개수 세기

문제 링크

풀이 참고1 : https://yabmoons.tistory.com/596
풀이 참고2 : https://ansohxxn.github.io/programmers/93/

문제 설명

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

---

입출력 예

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

풀이 코드

#include <string>
#include <vector>

using namespace std;

void DFS(int x, int y, vector<int>& answer, vector<vector<int>>& arr, int size)
{
    int sum = 0;
    // 현재 영역 순회
    for(int i = x; i < x + size; i++)
    {
        for(int j = y ; j < y + size; j++)
        {
            sum += arr[i][j];
        }
    }
    //0 혹은 1로만 이루어져있다면 정답 배열에 추가하고 종료
    if(sum == 0)
    {
        answer[0]++;
        return;
    }
    else if(sum == size * size)
    {
        answer[1]++;
        return;
    }
    
    // 그렇지 않다면 현재 영역을 4개의 영역으로 나누기
    DFS(x, y, answer, arr, size/2); // 2사분면
    DFS(x + size/2, y, answer, arr, size/2); // 1사분면
    DFS(x, y + size/2, answer, arr, size/2); // 3사분면
    DFS(x + size/2, y + size/2, answer, arr, size/2); // 4사분면
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2,0);
    int size = arr.size();
    DFS(0, 0, answer, arr, size);
    return answer;
}

• 문제의 핵심은 재귀호출이다. 처음 문제를 읽고 한 영역에 한 가지 수만 남을 때까지 어떻게 계속 나눌 것이며, 한 가지 수만 남아있다고 어떻게 판단할 것인가를 고민했다. while로 해야하나, 고민했는데 다른 풀이를 보니 결국 재귀호출이었다.

• 로직은 생각보다 간단하다. 문제 설명과 비슷하다.

  1. 현재 영역의 원소가 모두 0 혹은 1이 이라면, 해당하는 정답 배열에 ++한다.(종료 조건)
  2. 1번에 해당하지 않는다면, 현재 영역을 균일하게 4등분하고, 각 영역마다 1번을 실행한다.
  3. 종료 조건을 만족할 때까지 1~2를 반복한다.

• 모두 0 아니면 1 인지 판단하는 것은 원소들을 더해보면 된다. 모두 0이라면 그 합이 0일 것이고, 모두 1이라면 영역의 원소의 개수만큼 합이 나올 것이다.

• 그렇지 않다면 4개의 영역으로 나누어 재귀 호출을 하는데, 각 영역의 좌상단을 시작점으로 잡고 호출한다.