[BOJ] 백준 2630 색종이 만들기

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

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

한 변의 길이 N에 대해서 같은 색깔로 이루어져 있는지 검사합니다.

- 같은 색깔로 이루어진 경우에는 4등분 하지 않습니다.

- 같은 색깔로 이루어져 있지 않다면 4등분 합니다.

  이때, 분할정복을 착안해서 4등분된 곳의 좌측 상단 좌표와 영역의 길이를 넘겨줍니다.

  전달된 정보를 바탕으로 재귀적으로 색깔 확인 및 분할합니다.

  

: 한 변의 길이 N = 8

: 중간에 같은 색깔로 이루어진 경우 재귀 탐색을 멈춥니다.

: (길이 "1" 해당하는 일부 구간 생략)

- (0, 0, 8)

    - (0, 0, 4)

        - (0, 0, 2)

            - (0, 0, 1)

            - (0, 1, 1)

            - (1, 0, 1)

            - (1, 1, 1)

        - (0, 2, 2)

            - (0, 2, 1)

            - (0, 3, 1)

            - (1, 2, 1)

            - (1, 3, 1)

        - (2, 0, 2)

            - (2, 0, 1)

            - (2, 1, 1)

            - (3, 0, 1)

            - (3, 1, 1)

        - (2, 2, 2)

            - (2, 2, 1)

            - (2, 3, 1)

            - (3, 2, 1)

            - (3, 3, 1)

    - (0, 4, 4)

        - (0, 4, 2)

        - (0, 6, 2)

        - (2, 4, 2)

        - (2, 6, 2)

    - (4, 0, 4)

        - (4, 0, 2)

        - (4, 2, 2)

        - (6, 0, 2)

        - (6, 2, 2)

    - (4, 4, 4)

        - (4, 4, 2)

        - (4, 6, 2)

        - (6, 4, 2)

        - (6, 6, 2)

같은 색깔 여부는 별도의 좌표압축 없이 완전탐색으로 시간 범위내 가능합니다.

---

#include <stdio.h>
 
const int LM = 128;
int N, board[LM + 5][LM + 5];
int color[2]; // white(0), blue(1), 
 
bool isSameColor(int x, int y, int len) {
    // 한변의 길이가 1인 경우
    if (len == 1) return true;
 
    int pivot = board[x][y];
    for (int i = x; i < x + len; ++i) {
        for (int j = y; j < y + len; ++j) {
            // 색깔이 다른 경우
            if (pivot != board[i][j]) {
                return false;
            }
        }
    }
    return true;
}
 
void cut(int x, int y, int len) {
    if (isSameColor(x, y, len)) {
        // 해당 색깔의 개수 증가
        color[board[x][y]]++;
        return;
    }
    
    int half = len / 2;
    cut(x, y, half);
    cut(x + half, y, half);
    cut(x, y + half, half);
    cut(x + half, y + half, half);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &board[i][j]);
        }
    }
 
    cut(0, 0, N);
    printf("%d\n%d\n", color[0], color[1]);
}