BOJ 1780 - 종이의 갯수

www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

백준 1992 쿼드 트리 (www.acmicpc.net/problem/1992) 문제와 유사한 문제이다.

분할 정복 기법을 사용해야만 풀 수 있는 문제로,

쿼드 트리에서는 4분할을 했다면, 이 종이의 갯수 문제는 9분할을 해야한다.

 

시작 좌표를 처음에는 (0, 0) 으로 잡고 크기를 전체 크기(n) 으로 잡는다.

즉 (0, 0) 에서 부터 n * n 크기의 이차원 행렬을 전체 순회한뒤, 원소의 갯수가 다른게 하나라도 있으면 

분할 정복을 실시해야한다.

 

9분할을 해야하므로, 다음 번 호출시에는 size / 3 의 크기로 호출하는데

 

-1) y, x, size / 3

-2) y, x + size / 3, size / 3

-3) y, x + (size / 3) * 2, size / 3

 

-4) y + size / 3, x, size / 3

-5) y + size / 3, x + size / 3, size / 3

-6) y + size / 3, x + (size / 3) * 2, size / 3

 

-7) y + (size / 3) * 2, x, size / 3

-8) y + (size / 3) * 2, x + size / 3, size / 3

-9) y + (size / 3) * 2, x + (size / 3) * 2, size / 3

 

이런 방식으로 총 9번 호출한다.

9 * 9 크기의 행렬에서 위의 9번 호출을 좌표로 표시한다면

(0, 0, 3)

(0, 3, 3)

(0, 6, 3)

 

(3, 0, 3)

(3, 3, 3)

(3, 6, 3)

 

(6, 0, 3)

(6, 3, 3)

(6, 6, 3) 이 된다고 할 수 있다.

 

이 문제에서 주의할점은 -1, 0, 1 의 갯수를 셀때이다.

-1, 0, 1 의 갯수를 표현할 배열을 하나 선언하고 (int arr[3])

해당 크기의 행렬이 전부 같은 수이면 해당하는 인덱스를 증가시켜준다.

그리고 나서 return 으로 함수를 빠져나오는게 중요하다 (빠져 나오지 않으면 size = 1 까지 계속 카운팅됨)

그렇지 못해서 size 가 1까지 갔을때는, 해당 좌표의 값을 찾아내어 인덱스를 증가시킨다

 

n 의 최대 크기가 3^7 = 2187 이므로, 

2187 * 2187 = 4,782,969 이므로 

위와 같은 재귀함수를 호출하여도 충분히 제한 시간 내에 풀 수가 있다.

 

- c++

 

#include <bits/stdc++.h>
 
#define MAX 2188
 
using namespace std;
 
int n;
int adj[MAX][MAX];
int arr[3]; // -1, 0, 1
 
void divide_and_conquer(int y, int x, int size) {
    if (size == 1) {
        int num = adj[y][x];
        if (num == -1) arr[0]++;
        else if (num == 0) arr[1]++;
        else if (num == 1) arr[2]++;
        return;
    }
    
    bool minus = true, zero = true, one = true;
    for (int i = y; i < y + size; ++i) {
        for (int j = x; j < x + size; ++j) {
            if (adj[i][j] != -1) minus = false;
            if (adj[i][j] != 0) zero = false;
            if (adj[i][j] != 1) one = false; 
        }
    }
    
    if (minus) {
        arr[0]++;
        return;    
    }
    
    if (zero) {
        arr[1]++;
        return;
    } 
 
    if (one) {
        arr[2]++;
        return;
    }
    
    divide_and_conquer(y, x, size / 3);
    divide_and_conquer(y, x + size / 3, size / 3);
    divide_and_conquer(y, x + (size / 3) * 2, size / 3);
    
    divide_and_conquer(y + size / 3, x, size / 3);
    divide_and_conquer(y + size / 3, x + size / 3, size / 3);
    divide_and_conquer(y + size / 3, x + (size / 3) * 2, size / 3);
    
    divide_and_conquer(y + (size / 3) * 2, x, size / 3);
    divide_and_conquer(y + (size / 3) * 2, x + size / 3, size / 3);
    divide_and_conquer(y + (size / 3) * 2, x + (size / 3) * 2, size / 3);
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> adj[i][j];
        }
    }
    
    divide_and_conquer(0, 0, n);
    for (int i = 0; i < 3; ++i) cout << arr[i] << "\n"; 
    
    return 0;
}