백준 2630 - 색종이 만들기

C++

2630 번 - 색종이 만들기

문제

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오. 문제 출처

접근 방법

재귀함수를 사용한다. 시작 점을 저장하고, 시작 점과 다른 색을 인식하면, 1/4로 나눈다.
이때 나눌 크기와, 그 나눈 부분의 시작점을 인자로 주어 재귀함수를 반복한다.
만약 n의 크기가 1까지 작아지면, 더 이상 나눌 수 없으므로 그 위치의 색을 구별하여 해당 색종이의 색을 증가시켜 준다.

코드

#include <iostream>

using namespace std;

int n, graph[128][128], one, zero;      //처음 색종이의 크기, 색종이, 파란색, 하얀색
int result;
void recur(int n, int y, int x);
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
		}
	}
	recur(n, 0, 0);
	cout << zero << "\n";
	cout << one;
	
}

void recur(int n, int y, int x) {
	if (n == 1) {                   //크기가 1이면, 더 이상 나눌 수 없으므로 해당 색을 판별
		if (graph[y][x]) {
			one++;
		}
		else {
			zero++;
		}
		return;
	}
	int first;                      //시작점. 이 시작 점의 색을 기준으로 다른 색이 나오는지 판별한다.
	first = graph[y][x];
	for (int i = y; i < y + n; i++) {
		for (int j = x; j < x + n; j++) {
			if (graph[i][j] != first) {
				recur(n / 2, y , x);                    // 1/4의 왼쪽 위
				recur(n / 2, y + (n/2) , x );           // 1/4의 왼쪽 아래
				recur(n / 2, y , x + (n/2));            // 1/4의 오른쪽 위
				recur(n / 2, y + (n/2) , x + (n/2));    // 1/4의 오른쪽 아래
				return;
			}
		}
	}
	if (first == 1) {           //여기 까지 왔다는 것은 해당 n크기 내부의 색이 다 같다는 것이므로, 해당 색의 색종이의 크기를 더해준다.
		one++;
	}
	else {
		zero++;
	}
	return;
}

후기 및 개선할 점