(c++) BOJ 2630번: 색종이 만들기

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

---

 

 

문제 개요

 

쿼드 트리란 대량의 좌표 데이터를 메모리 안에 압축하기 위해 사용하는 기법입니다.

 

주어진 공간을 4개로 분할하게 되는데 같은 데이터만 모일 때까지 재귀적으로 분할하게 됩니다.

 

위의 그림이 쿼드 트리로 변환하는 과정이다.

 

크기의 절반으로 분할해가면서 진행된다는 것을 알고 코드로 보자.

 

 

 

코드

 

 

분할한 정사각형의 처음 숫자와 다른 숫자가 나오면 4개의 정사각형으로 분할하는 부분이 중요하다.

 

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

int paper[MAX_N][MAX_N];
// 색종이 개수
int white, blue = 0;

void tree(int y, int x, int size) {
    int color = paper[y][x];
    for (int dy = y; dy < y + size; dy++) {
        for (int dx = x; dx < x + size; dx++) {
            if (paper[dy][dx] != color) {
                int half = size / 2;
                tree(y, x, half);
                tree(y, x + half, half);
                tree(y + half, x, half);
                tree(y + half, x + half, half);
                return;
            }
        }
    }
    if (color == 0) {
        white += 1;
    } else blue += 1;
}

int main(void) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> paper[i][j];
        }
    }
    tree(0, 0, n);
    cout << white << '\n' << blue;
}