[백준/C++] 2630번: 색종이 만들기 - 분할 정복과 재귀의 정석

1. 문제 정보

• 문제 번호: 2630번
• 문제 이름: 색종이 만들기
• 문제 요약: N X N 크기의 종이가 주어질 때, 모든 칸의 색이 같지 않으면 4등분하여 각각의 조각에 대해 같은 과정을 반복한다. 최종적으로 잘린 단색 색종이의 개수를 구하라.

2. 핵심 알고리즘: 분할 정복 (Divide and Conquer)

분할 정복은 말 그대로 "나누어서 정복한다"는 뜻입니다. 이 문제에서는 다음과 같은 3단계를 거칩니다.

1. Divide (분할): 현재 종이가 단색이 아니라면, 가로세로를 반으로 잘라 4개의 작은 사각형으로 나눕니다.
2. Conquer (정복): 나뉜 4개의 사각형에 대해 다시 같은 과정을 수행합니다. (재귀 호출)
3. Combine (결합): 단색으로 확인된 종이의 개수를 각각 카운트하여 합칩니다.

 

3. C++ 꿀팁: vector::assign()으로 2차원 배열 만들기

보통 2차원 배열을 만들 때 int arr[128][128]처럼 고정 크기를 잡기도 하지만, 입력값 $N$에 딱 맞게 동적으로 할당하고 싶을 때 vector의 assign()이 아주 유용합니다.

 

왜 assign()인가?

• 초기화와 할당을 동시에: 단순히 크기만 키우는 게 아니라, 원하는 값으로 꽉 채울 수 있습니다.
• 동적 할당의 편리함: new나 malloc처럼 직접 메모리를 해제해 줄 필요가 없습니다. 벡터가 알아서 관리하니까요.
• 구조: paper.assign(N, vector<int>(N))
  • 첫 번째 인자: 행(Row) 개수
  • 두 번째 인자: 각 행에 들어갈 열(Column) 벡터 (크기와 초기값 지정 가능)

 

4. 코드 구현

#include <iostream>
#include <vector>

using namespace std;

int wc = 0, bc = 0; // wc: white(0) count, bc: blue(1) count
vector<vector<int>> paper;

// 현재 영역이 모두 같은 색인지 확인하는 함수
bool check_same_color(int x, int y, int size) {
    int color = paper[x][y];
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (paper[i][j] != color) return false;
        }
    }
    return true;
}

// 색종이를 자르는 재귀 함수
void cut(int x, int y, int size) {
    // 1. 현재 영역이 모두 같은 색이라면 해당 색 카운트 후 종료
    if (check_same_color(x, y, size)) {
        if (paper[x][y] == 0) wc++;
        else bc++;
        return; 
    }

    // 2. 다른 색이 섞여 있다면 4등분하여 재귀 호출
    int half = size / 2;
    cut(x, y, half);             // 왼쪽 위
    cut(x, y + half, half);      // 오른쪽 위
    cut(x + half, y, half);      // 왼쪽 아래
    cut(x + half, y + half, half); // 오른쪽 아래
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    // 벡터 공간 할당 및 초기화
    paper.assign(N, vector<int>(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> paper[i][j];
        }
    }

    // (0, 0) 좌표부터 N 크기의 색종이 탐색 시작
    cut(0, 0, N);
    
    cout << wc << "\n" << bc << "\n";

    return 0;
}

 

5. 배운 점 & 회고 (TIL) ✍️

① 4분할의 좌표 계산

사각형을 4개로 쪼갤 때 시작 좌표를 잡는 로직을 머릿속으로 그려보는 연습이 되었습니다.

• (x, y)
• (x, y + half)
• (x + half, y)
• (x + half, y + half) 이 규칙은 나중에 쿼드 트리(Quad Tree)나 다른 격자형 분할 정복에서도 그대로 쓰이는 핵심 로직

 

② 재귀의 탈출 조건 (Base Case)

분할 정복에서 가장 중요한 건 "언제 멈출 것인가?"입니다. 이 문제에서는 check_same_color가 true를 반환하거나 종이의 크기가 1이 되었을 때(크기가 1이면 무조건 단색이므로 check_same_color에서 true가 나옴) 멈추게 됩니다. 탈출 조건을 명확히 잡아야 무한 루프나 스택 오버플로우를 피할 수 있다는 걸 다시 느꼈습니다.

③ 유연한 벡터 활용

assign()을 통해 전역으로 선언된 2차원 벡터를 main 함수 안에서 입력 크기에 맞춰 동적으로 재설정하는 방법이 아주 깔끔하다는 것을 배웠습니다. 메모리 관리 측면에서도 안전.