백준_2630 : 색종이 만들기 - C++

문제

---

문제 해석

- 색종이를 종이 내에 같은 색만이 남을 때 까지 1/4로 계속 잘랐을 때 휜색과 파란색 정사각형 종이가 몇장씩 있는지 알아내는 문제이다.

---

알고리즘

- 재귀를 통한 분할정복으로 문제를 해결 하면 된다.

- 종이의 시작 좌표와 크기를 넘겨 받은 후 해당 종이의 색이 같은지를 확인한다.

  - 이때 하나라도 다른 색이 끼여 있다면 종이를 4등분 하여 같은 동작을 반복 한다.

    - 방법은 4등분 한 종이의 시작 좌표(가장 좌측 상단의 x, y 좌표)와 자른 후의 size 를 재귀함수에 넘겨 주면 된다.

  - 모든 색이 같다면 무슨색인지 조사하여 해당 색의 종이 수를 하나 늘려 준다.

---

코드

#include <iostream>
using namespace std;

int paper[130][130];
int blue=0, white=0, N;

void cut(int start_x, int start_y, int size){
    bool flag = true;
    for(int i = start_x; i < start_x+size; i++){
        for(int j = start_y; j < start_y+size; j++){
            if(paper[i][j] != paper[start_x][start_y]){
                cut(start_x, start_y, size/2);
                cut(start_x + size/2, start_y, size/2);
                cut(start_x, start_y + size/2, size/2);
                cut(start_x + size/2, start_y + size/2, size/2);
                flag = false;
                break;
            }
        }
        if(!flag) break;
    }
    if(flag){
        if(paper[start_x][start_y] == 1){
            blue += 1;
        } else {
            white += 1;
        }
    }
}

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