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

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

// 프로그래머스 68936 - 쿼드압축 후 개수 세기 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/68936

// 문제 설명
// 0과 1로 이루어진 2^n x 2^n 배열 arr을 쿼드 트리 방식으로 압축한다.
// 어떤 정사각형 영역의 값이 모두 같으면 그 영역을 하나의 값으로 압축하고,
// 하나라도 다르면 4개의 같은 크기 정사각형으로 쪼갠 뒤 각각을 다시 압축한다.
// 압축이 끝난 뒤 남은 0의 개수와 1의 개수를 [0의 개수, 1의 개수]로 반환하라.

// 제약 조건
// arr의 행/열 길이는 1 이상 1,024 이하인 2의 거듭제곱 (1, 2, 4, ..., 1024)
// arr은 정사각형이고 각 원소는 0 또는 1

// Example
// Input : [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]
// Output: [4, 9]
//
// Input : [[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]]
// Output: [10, 15]

// 접근 — 분할 정복 상향식: 자식 4개의 반환값으로 병합을 판정
// "영역이 균일한가"를 매번 전부 훑으면 각 레벨에서 O(n^2)이라 O(n^2 log n)이 된다.
// 대신 1x1까지 내려간 뒤 올라오면서 자식의 반환값만 비교한다.
// 1) quad는 "이 영역이 하나로 압축되면 그 값, 쪼개졌으면 -1"을 반환한다.
//    -1은 "이 아래에 서로 다른 값이 섞여 있다"는 센티넬이다.
// 2) size == 1이면 그 칸을 개수에 더하고 자기 값을 반환한다(재귀 바닥).
// 3) 네 자식 반환값이 -1이 아니고 모두 같으면 병합 가능 — 이미 세어 둔 자식 4개를
//    하나로 접기 위해 cnt[값] -= 3을 하고 그 값을 반환한다.
//    자식 중 하나라도 -1이거나 값이 갈리면 -1을 반환해 상위 병합을 막는다.
// 4) 재귀 깊이는 log2(1024) + 1 = 11로 스택 여유가 충분하고,
//    개수 상한은 1024^2 = 1,048,576이라 int로 안전하다.
// 시간 O(n^2) (칸마다 정확히 한 번), 공간 O(log n) 스택

#include <vector>

using namespace std;

vector<vector<int>> board;                         // 재귀 인자 복사를 피해 전역에 한 번만
int cnt[2];                                        // cnt[0] = 0의 개수, cnt[1] = 1의 개수

int quad(int y, int x, int size)                   // 압축된 값, 쪼개졌으면 -1
{
    if (size == 1)
    {
        cnt[board[y][x]]++;                        // 바닥에서 일단 다 세어 둔다
        return board[y][x];
    }

    int half = size / 2;
    int a = quad(y, x, half);
    int b = quad(y, x + half, half);
    int c = quad(y + half, x, half);
    int d = quad(y + half, x + half, half);

    if (a != -1 && a == b && b == c && c == d)     // -1 검사를 먼저 (cnt[-1] 방지)
    {
        cnt[a] -= 3;                               // 자식 4개를 1개로 접기: -4 + 1
        return a;
    }

    return -1;
}

vector<int> solution(vector<vector<int>> arr)
{
    board = arr;
    cnt[0] = cnt[1] = 0;

    quad(0, 0, arr.size());

    return { cnt[0], cnt[1] };
}

정리

• 커리큘럼 105번. 쿼드 트리는 “영역이 균일하면 접고, 아니면 4등분해서 각각 반복”이라는 정의 자체가 재귀라서 문제 문장을 그대로 함수로 옮기면 골격이 완성된다. 어려운 지점은 재귀 구조가 아니라 개수를 어느 시점에 세느냐다.
• 정의를 그대로 따라 하향식으로 쓰면 “이 영역이 균일한가”를 확인하려고 매 레벨에서 영역 전체를 훑게 되고, 레벨마다 O(n²)이 붙어 O(n² log n) — 1024²×11 ≈ 1,150만이라 통과는 하지만 필요 없는 비용이다. 상향식으로 뒤집어 자식의 반환값만 비교하면 칸마다 정확히 한 번씩 방문해 O(n²) = 약 105만으로 줄어든다. “위에서 검사”를 “아래에서 보고”로 바꾸는 이 전환이 분할 정복의 상수를 결정한다.
• 반환값 하나가 두 가지 정보를 나른다: 압축된 값(0/1)이면 균일, -1이면 쪼개짐. 균일 여부를 별도의 bool로 들고 다니는 대신 값 범위 밖의 -1을 센티넬로 쓰는 방식으로, 부모는 a == b == c == d라는 비교 한 줄로 “넷 다 균일하고 값도 같다”를 판정한다. 상태 두 개를 한 반환값에 접는 건 string::find가 실패를 npos로 알리는 것과 같은 관용.
• cnt[a] -= 3이 이 풀이의 계산 핵심이다. 바닥에서 이미 자식 4개를 세어 뒀으므로 병합은 “4개 취소 + 1개 추가” = -3. 세고 나서 되돌리는 방식이라 “이 영역이 최종적으로 몇 개로 남는가”를 미리 알 필요가 없어진다.
• 비교 순서를 a != -1부터 두는 게 안전 장치다. 이 검사를 빼면 자식 넷이 모두 쪼개진 경우(-1 == -1 == -1 == -1)에 병합 조건이 참이 되어 cnt[-1]로 배열 범위를 벗어나 쓴다. 값이 조용히 망가지는 종류의 버그라, 센티넬을 쓸 때는 “센티넬끼리 같다”가 참이 되는 경로를 항상 먼저 막는다.
• 상한 점검 두 가지. 재귀 깊이는 log₂(1024) + 1 = 11단계로 스택 걱정이 없다(정사각형 크기가 2의 거듭제곱이라 size / 2가 언제나 정확히 나뉘고, 1에서 바닥에 닿는다). 개수 상한은 전부 쪼개진 최악에 1024² = 1,048,576이라 int로 충분하다. board를 전역에 두고 좌상단 좌표와 변 길이만 넘기는 것도 1024×1024 배열이 재귀마다 복사되지 않게 하려는 것.
• 검증: 예제 2개([4,9], [10,15])와 경계 케이스 — 1×1 [[1]](→ [0,1])·[[0]](→ [1,0]), 2×2 균일(→ [0,1])·완전 교차(→ [2,2]), 1024×1024 전부 0(→ [1,0])·랜덤 모두 10ms 수준 통과. 추가로 하향식(매 레벨 전체 스캔) 구현을 따로 만들어 크기·밀도를 무작위로 바꾼 격자 300개에서 두 결과가 전부 일치함을 확인 (MSVC /std:c++17 /O2 컴파일·실행).

핵심 요약 — 하향식으로 매 레벨 균일성을 훑으면 O(n² log n), 자식 반환값으로 판정하는 상향식은 O(n²)이다. 반환값에 “압축된 값 또는 -1(쪼개짐)”을 실어 비교 한 줄로 병합을 판정하고, 이미 센 자식 4개를 cnt -= 3으로 하나로 접는다. -1 검사를 조건 앞에 두지 않으면 자식이 모두 쪼개진 경우 cnt[-1]로 범위를 벗어난다.