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

🌽 문제

🥕 입출력

🥔 풀이

분할 정복 알고리즘을 적용하는 문제다.
시작점 (y, x)와 size를 넘겨주는 재귀 함수를 작성했다.

해당 구간 안에 다른색이 섞여있다면 시작점을 기준으로 4등분한 뒤
각각의 영역을 다시 재귀 함수로 넘겨주는 방식이다.

해당 영역이 모두 같은 색으로 이루어져있다면,
색깔에 맞는 cnt 수를 하나씩 늘리기를 반복한다.

🥬 코드

#include <iostream>
#include <vector>
using namespace std;

int n;
int arr[130][130] = { 0, };
int wh = 0;
int bl = 0;

void getCnt(int y, int x, int size, bool flag = false) {
	int color = arr[y][x];
	for (int i = y; i < y + size; i++) {
		if (flag) break;
		for (int j = x; j < x + size; j++) {
			if (arr[i][j] != color) {
				flag = true;
				break;
			}
		}
	}

	if (!flag) {
		if (color == 0) wh++;
		else bl++;
	}
	else {
		int nsize = size / 2;
		getCnt(y, x, nsize);
		getCnt(y, x + nsize, nsize);
		getCnt(y + nsize, x, nsize);
		getCnt(y+ nsize, x+ nsize, nsize);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	getCnt(0, 0, n);
	cout << wh << "\n" << bl;

	return 0;
}

👓 GPT 추천 코드

void getCnt(int y, int x, int size) {
    int color = arr[y][x];
    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            if (arr[i][j] != color) {
                int nsize = size / 2;
                getCnt(y, x, nsize);
                getCnt(y, x + nsize, nsize);
                getCnt(y + nsize, x, nsize);
                getCnt(y + nsize, x + nsize, nsize);
                return;
            }
        }
    }
    if (color == 0) wh++;
    else bl++;
}

🥜 채점