[백준/C++] 2630번: 색종이 만들기

문제

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

---

문제 요약

N × N 개의 정사각형 칸들로 이루어진 정사각형 모양의 종이가 주어졌을 때, 각 정사각형들은 하얀색 또는 파란색으로 칠해져 있다.

 

주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들어야 한다.

 

 

잘라진 하얀색 색종이와 파란색 색종이의 개수를 출력한다.

---

코드

#include <iostream>
#include <vector>

#define MAX_N 128

using namespace std;

int paper[MAX_N + 1][MAX_N + 1];

int n;

int blue_cnt, white_cnt;

void search(int x, int y, int sz) {
	bool is_cut = false;
	int first = paper[x][y];

	// 해당 범위의 배열 내 다른 요소가 있는지 체크 
	for (int i = x; i < x + sz; i++) {
		for (int j = y; j < y + sz; j++) {
			if (paper[i][j] != first) {
				is_cut = true;
				break;
			}
		}
	}

	// 잘라야 한다면,
	if (is_cut) {
		search(x, y, sz / 2);
		search(x, y + sz / 2, sz / 2);
		search(x + sz / 2, y, sz / 2);
		search(x + sz / 2, y + sz / 2, sz / 2);
	}

	// 더이상 자르지 않아도 된다면,
	else {
		if (first == 1) {
			blue_cnt++;
		}
		else {
			white_cnt++;
		}
	}
}

int main() {
	cin >> n;

	// 2차원 배열에 입력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> paper[i][j];
		}
	}
	
	// 탐색
	search(0, 0, n);

	cout << white_cnt << "\n";
	cout << blue_cnt;

	return 0;
}

---

코드 설명

1. 2차원 배열에 색종이 정보를 입력 받는다.

 

2. 분할 상환 기법을 이용하여 해당 범위의 배열이 다른 요소가 존재하는 지 체크한다.

 

3. 다른 요소가 존재해서 잘라야 한다면, 4개의 배열로 잘라서 각각 재귀적으로 탐색한다.

 

4. 다른 요소가 존재하지 않는다면, 배열 내 요소를 체크하여 해당 색종이 개수를 증가시킨다.

 

5. 각 색종이 개수를 출력한다.