안녕하세요! 오늘은 백준 알고리즘 문제 중 "종이의 개수"를 풀어보겠습니다. 이 문제는 분할 정복과 재귀의 기본을 탄탄하게 다질 수 있는 좋은 문제입니다.

백준 1780: 종이의 개수

1. 문제 소개

문제 번호: 1780
문제명: 종이의 개수
난이도 (티어): Silver II
사용 언어: C++
실행 시간: 360 ms
메모리: 20928 KB

문제 요약

주어진 N x N 크기의 행렬은 -1, 0, 1 세 가지 값으로 채워져 있습니다. 이 행렬을 다음과 같은 규칙에 따라 분할하려고 합니다.

만약 행렬이 모두 같은 값으로 이루어져 있다면, 더 이상 분할하지 않습니다.
그렇지 않다면, 행렬을 동일한 크기의 9개의 서브 행렬로 나눕니다.

이 과정을 반복하여 최종적으로 만들어지는 다음과 같은 크기의 행렬들의 개수를 세는 문제입니다.

-1로만 채워진 행렬
0으로만 채워진 행렬
1로만 채워진 행렬

2. 접근 방법

이 문제는 주어진 행렬을 크기가 1이 될 때까지 반복적으로 분할하는 과정을 포함하므로, 분할 정복(Divide and Conquer) 기법을 활용하는 것이 자연스럽습니다. 또한, 분할된 각 부분 행렬에 대해 동일한 작업을 수행해야 하므로 재귀(Recursion) 함수를 사용하여 문제를 해결할 수 있습니다.

왜 이 방법을 선택했나?

분할 정복: 문제의 정의 자체가 '분할'을 명시하고 있으며, 각 부분 문제(서브 행렬)를 해결하여 전체 문제의 해를 구하는 방식은 분할 정복의 핵심 아이디어와 일치합니다.
재귀: 분할된 서브 행렬들에 대해서도 동일한 규칙을 적용해야 하므로, 재귀 함수를 사용하면 코드를 간결하고 효율적으로 작성할 수 있습니다. 각 재귀 호출은 하나의 서브 행렬을 처리하며, 만약 해당 서브 행렬이 단색이 아니면 다시 9개의 더 작은 서브 행렬로 분할하여 재귀 호출을 이어갑니다.

3. 풀이 과정

핵심 아이디어는 주어진 크기의 종이(행렬의 부분)를 검사하여, 그것이 단일 색상인지 아니면 여러 색상이 섞여 있는지를 판단하는 것입니다.

dividePaper(x, y, size) 함수 정의:
- 이 함수는 (x, y) 좌표에서 시작하는 size x size 크기의 종이가 단일 색상으로 이루어져 있는지 판별하는 역할을 합니다.
- 먼저, 해당 종이 영역의 첫 번째 칸(paper[x][y])의 색상(firstColor)을 기준으로 잡습니다.
단색인지 검사:
- size x size 영역 전체를 순회하면서 firstColor와 다른 색상이 있는지 확인합니다.
- 만약 하나라도 다른 색상이 발견된다면 (즉, 섞여 있다면):
  - 해당 종이는 더 이상 하나의 색상으로 간주될 수 없습니다.
  - 즉시 9개의 size/3 x size/3 크기의 서브 영역으로 분할합니다.
  - 분할된 각 서브 영역에 대해 dividePaper 함수를 재귀적으로 호출합니다.
  - 이후, 현재 dividePaper 함수는 더 이상 수행할 일이 없으므로 return합니다. (핵심: 불필요한 연산 제거)
단색인 경우:
- size x size 영역 전체를 순회했는데도 firstColor와 다른 색상이 하나도 발견되지 않았다면, 해당 종이는 firstColor로만 이루어진 단일 색상입니다.
- firstColor 값에 따라 one_cnt, minus_one_cnt, zero_cnt 중 해당 카운트를 1 증가시킵니다.
초기 호출:
- main 함수에서는 입력으로 주어진 N x N 행렬 전체에 대해 dividePaper(0, 0, N)를 호출하여 분할 과정을 시작합니다.

핵심 아이디어

조기 종료 (Early Exit): 한 번이라도 다른 색상이 발견되면 즉시 9분할로 넘어가고 현재 함수를 종료함으로써, 불필요한 검사를 줄이고 효율성을 높입니다.
재귀적 분할: 종이가 단색이 아닐 경우, 자동으로 9개의 더 작은 종이로 분할하여 각 부분을 동일한 방식으로 처리합니다.

주의할 점

배열 크기: 문제에서 N은 최대 2187까지 가능하므로, 재귀 깊이가 깊어질 수 있습니다. 따라서 배열을 선언할 때는 충분한 크기(예: 2200x2200)로 잡아주어야 합니다.
정수 나눗셈: size / 3과 같이 정수 나눗셈을 사용하여 서브 영역의 크기를 계산할 때 값이 정확히 나누어 떨어져야 합니다. 문제의 제약 조건을 만족한다면 이는 문제가 되지 않습니다.
C++ 표준 라이브러리 사용: bits/stdc++.h를 포함하여 필요한 모든 표준 라이브러리를 사용할 수 있게 합니다. ios::sync_with_stdio(false); cin.tie(nullptr);를 사용하여 입출력 속도를 최적화하는 것이 좋습니다.

4. 코드 설명

#include <bits/stdc++.h>
using namespace std;

/*
- 첫 칸의 색을 기준(firstColor)으로 잡음
- 순회 중 하나라도 다른 값이 나오면
  → "섞임"이 즉시 확정 → 바로 9 구역으로 등분 재귀
- 끝까지 다 돌았으면 전부 같은 색
- 불필요한 연산 제거 (early exit)

- dividePaper(x, y, size)는
  → (x, y)에서 시작하는 size x size 종이가
     하나로 가능한지 판별하는 함수

- 격자 내 모두 단일 번호면: 해당 번호 종이 1장 카운트
- 다른 번호가 섞여 있으면: 9개의 size/3 정사각형으로 분할
*/

int N;
int paper[2200][2200]; // N의 최대값(2187)보다 크게 선언
int one_cnt = 0;
int minus_one_cnt = 0;
int zero_cnt = 0;

// (x, y) 좌표에서 시작하는 size x size 영역을 검사하고 분할하는 재귀 함수
void dividePaper(int x, int y, int size) {
    int firstColor = paper[x][y];  // 현재 영역의 기준 색상

    // 현재 영역이 단색인지 검사
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {

            // 하나라도 기준 색과 다르면 → 섞임 확정
            if (paper[i][j] != firstColor) {

                // 섞임이 확정되었으므로, 9개의 영역으로 분할하여 재귀 호출
                int trisection = size / 3; // 한 변을 3등분한 크기
                
                // 3x3 격자로 분할하여 각 부분에 대해 재귀 호출
                for(int m = 0; m < 3; m++)
                    for(int n = 0; n < 3; n++){
                        // 각 서브 영역의 시작 좌표와 크기를 전달
                        dividePaper(x + m * trisection, y + n * trisection, trisection);
                    }
                // 9개의 재귀 호출이 끝났으므로, 현재 함수는 더 이상 할 일이 없음. 즉시 반환.
                return;  
            }
        }
    }

    // 루프를 모두 통과했다는 것은 현재 영역이 전부 firstColor와 같다는 의미
    // 단색 종이이므로 해당 색상의 카운트를 증가시킴
    switch(firstColor){
        case 1:
            one_cnt++;
            break;
        case -1:
            minus_one_cnt++;
            break;
        case 0:
            zero_cnt++;
    }
}

int main() {
    // 입출력 속도 최적화
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N; // 행렬의 크기 입력
    // N x N 행렬의 값들을 입력받아 paper 배열에 저장
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> paper[i][j];
        }
    }

    // 전체 N x N 행렬에 대해 분할 시작
    dividePaper(0, 0, N);

    // 최종 카운트 결과 출력
    cout << minus_one_cnt << '\n' << zero_cnt << '\n' << one_cnt;
    return 0;
}

코드 설명:

paper[2200][2200] : N의 최대값(2187)을 고려하여 충분히 큰 크기로 선언했습니다.
one_cnt, minus_one_cnt, zero_cnt : 각각 1, -1, 0으로 이루어진 종이의 개수를 저장하는 변수입니다.
dividePaper(int x, int y, int size) :
- firstColor를 기준으로 삼아 size x size 영역을 검사합니다.
- 만약 다른 색상이 발견되면, size / 3 크기의 9개 서브 영역으로 분할하고 각 영역에 대해 재귀 호출합니다. 이 경우 return하여 불필요한 검사를 생략합니다.
- 모두 같은 색상이면 해당 cnt를 증가시킵니다.
main() :
- 입출력 최적화 설정을 합니다.
- N과 행렬 paper의 값을 입력받습니다.
- dividePaper(0, 0, N)를 호출하여 전체 행렬에 대한 처리를 시작합니다.
- 최종적으로 세 가지 색상의 종이 개수를 출력합니다.

5. 복잡도 분석

시간 복잡도: O(N^2 log N) (또는 O(N^2))
- 각 재귀 호출은 size x size 영역을 한 번씩 검사합니다.
- 단색인 경우, O(size^2)의 검사가 필요합니다.
- 색상이 섞인 경우, size가 size/3으로 줄어드는 9번의 재귀 호출이 발생합니다.
- 모든 노드(크기 1x1 종이)는 한 번씩 방문되고, 각 종이의 색상을 확인하는 데 O(size^2) 시간이 걸린다고 볼 수 있습니다.
- 좀 더 정확하게는, 전체 N x N 행렬에서 각 원소는 최대 log_3(N) 깊이의 재귀 호출에서 검사될 가능성이 있습니다. 따라서 총 시간 복잡도는 O(N^2 log N)으로 볼 수도 있지만, 각 노드를 한 번씩만 방문하고 특정 깊이 이상 내려가지 않으므로 O(N^2)으로 보기도 합니다. (각 원소는 한 번씩만 firstColor 비교를 당함)
공간 복잡도: O(N^2) (배열 저장) + O(log N) (재귀 스택)
- paper 배열을 저장하는 데 O(N^2)의 공간이 필요합니다.
- 재귀 호출의 최대 깊이는 N이 3으로 계속 나누어질 때의 깊이이므로 O(log N)입니다.
- 따라서 전체 공간 복잡도는 O(N^2)입니다.

6. 배운 점

이 문제를 풀면서 분할 정복과 재귀의 강력함을 다시 한번 느낄 수 있었습니다.

재귀적 사고: 복잡한 문제를 작은 단위의 동일한 문제로 쪼개어 생각하는 재귀적 사고방식이 매우 중요함을 알게 되었습니다.
조기 종료의 중요성: 불필요한 연산을 최대한 줄이는 early exit 패턴이 알고리즘의 효율성을 크게 향상시킬 수 있다는 것을 배웠습니다.
매개변수 전달: 재귀 함수에서 x, y, size와 같은 매개변수를 정확하게 전달하여 서브 문제를 올바르게 정의하는 것이 핵심입니다.
배열 크기 고려: 재귀 깊이나 문제의 최대 입력값을 고려하여 배열을 충분한 크기로 선언하는 습관을 들여야 합니다.

이 문제는 다른 분할 정복 문제나 트리 구조를 다루는 문제에 적용될 수 있는 좋은 기반이 됩니다.

오늘 포스팅은 여기까지입니다. 감사합니다!