(c++) BOJ 1780번: 종이의 개수

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

1780번: 종이의 개수

 

 

---

 

 

문제 개요

 

 

쿼드 트리는 원래 4개로 나누는데 이 문제는 9개로 나누는 문제이다.

 

쿼드 트리 코드에서 재귀 부분만 코드를 고친다면 쉽게 해결 가능하다.

 

재귀 부분은 이중 for문을 이용해서 구현했다. (9번 코딩해도 문제없다.)

만일 N이 9일 경우 (0, 0), (0, 3), (0, 6) ... ,(6, 6) 순서로 재귀한다.

 

코드

 

 

#include <bits/stdc++.h>
#define MAX_N 2187

using namespace std;

int paper[MAX_N][MAX_N];
// m_0 = -1, zero = 0, p_0 = +1
int m_o, zero, p_o = 0;

void tree(int y, int x, int size) {
    int num = paper[y][x];
    for (int dy = y; dy < y + size; dy++) {
        for (int dx = x; dx < x + size; dx++) {
            if (paper[dy][dx] != num) {
                int th = size / 3;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        tree(y + (th * i), x + (th * j), th);
                    }
                }
                return;
            }
        }
    }
    if (num == -1) {
        m_o += 1;
    } else if (num == 0) {
        zero += 1;
    } else p_o += 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 << m_o << '\n' << zero << '\n' << p_o;
}