백준 2630 - 색종이 만들기 [C++]

새해 기념 첫번째 포스팅입니다.

작년 KOI 중등부 첫번째 문제도 비슷했던 것으로 기억이 나는데, 이 문제가 좀 더 쉬웠던 것 같습니다.

문제의 목표는 자른 색종이가 전부 하얀색이거나 파란색이 될때까지 색종이를 반으로 계속 자르고 나서 그 잘라진 하얀색 / 파란색 색종이의 개수를 구하는 것입니다. 

---

#풀이

한 변의 길이가 모두 2의 거듭제곱 형태이기 때문에, 좌표를 바꾸고 길이를 계속 절반으로 하는 재귀함수를 구현하면 될 것 같습니다.

구체적으로는,

1. N x N 사이즈의 정사각형 내에 있는 모든 칸의 색을 체크합니다.

2 - 1. 만약 모든 색이 같다면, 해당 색의 색종이 개수에 1을 더해줍니다.

2 - 2. 만약 한 칸이라도 색이 다르다면, N x N 사이즈의 색종이를 위 그림처럼 (N/2) x (N/2) 사이즈의 색종이 4개로 잘라서 1번부터 반복하고 종료해줍니다.

* 종료를 안하면 색종이가 한 색깔이 아니여도 색깔의 개수를 올려주므로 반드시 종료해줘야 합니다.

 

1 x 1 사이즈의 색종이에서는 반드시 그 칸의 색이 곧 해당 색종이의 색이기 때문에, 다른 조건을 넣을 필요는 없습니다.

---

#코드

 

#include <stdio.h>

const int N = (1e2 + 1) * 2;

int n = 0, w = 0, b = 0;//w = 하얀색 색종이 개수, b = 파란색 색종이 개수
int mapp[N][N] = {{0}};

void paper(int x, int y, int l);//하얀색, 파란색 색종이의 개수를 구할 재귀함수

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            scanf("%d", &mapp[i][j]);
    }
    paper(0, 0, n);
    printf("%d\n%d", w, b);
    return 0;
}

void paper(int x, int y, int l) {//l = 색종이의 한 변의 길이
    int newlen = l / 2;
    bool def = mapp[x][y];//현재 색종이의 맨 왼쪽 위 칸의 색
    for (int i = x; i < x + l; ++i) {
        for (int j = y; j < y + l; ++j) {
            if (mapp[i][j] != def) {//한 칸이라도 색이 다르면 색종이를 4개로 자름
                paper(x, y, newlen);
                paper(x + newlen, y, newlen);
                paper(x, y + newlen, newlen);
                paper(x + newlen, y + newlen, newlen);
                return;
            }
        }
    }
    //모든 칸의 색이 같으면 그 색의 개수를 올려줌
    if (def == 0)
        ++w;
    else
        ++b;
}