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

문제 바로가기

처음 이 문제를 풀 때는 재귀함수를 사용하지 않으려고 했다.

재귀함수를 사용하지 않고 반복문을 사용하여 잘게 쪼개는 방식으로 하려고 했지만,

마음처럼 되지 않아 재귀함수로 돌아왔다.

 

int area = N * N;
int* square = new int[area];
for (int i = 0; i < area; i++)
	cin >> square[i];

N * N 크기의 int 배열을 동적으로 할당하여, 종이의 색을 저장했다.

int count[2] = { 0, 0 }; // { W, B }
int sides[2] = { N, N };

count 배열의 첫 번째 요소는 흰 색종이의 갯수를, 두 번째 요소는 파란 색종이의 갯수를 저장한다.

sides는 한 변의 길이를 저장하는 배열로, 첫 번째 요소는 처음 입력된 길이인 N을 그대로 유지하고 두 번째 요소는 함수 호출이 반복 될 때 반감된다.

void chop(int* pivot, int* sides, int* data, int* count) {
	// Step 1. Verification
	bool isAccepted = true;
	int type = data[pivot[1] * sides[0] + pivot[0]];
	for (int dy = 0; dy < sides[1] && isAccepted; dy++) {
		for (int dx = 0; dx < sides[1] && isAccepted; dx++) {
			int chg_x = pivot[0] + dx;
			int chg_y = pivot[1] + dy;

			if (data[chg_y * sides[0] + chg_x] != type)
				isAccepted = false;
		}
	}

	// Step 2. If it is accepted, count up.
	if (isAccepted) {
		count[type]++;
		return;
	}

	// Step 3. If it is not accepted, Chop it up
	int newSides[2] = { sides[0], sides[1] / 2 };
	int newPivots[4][2] = {	{pivot[0]		,	pivot[1]		},
				{pivot[0] + newSides[1] ,	pivot[1]		},
				{pivot[0]		,	pivot[1] + newSides[1]	},
				{pivot[0] + newSides[1] ,	pivot[1] + newSides[1]	} };
	for (auto& newPivot : newPivots)
		chop(newPivot, newSides, data, count);
}

chop 함수는 아무것도 반환하지 않으며, 대신 조건에 따라 count 배열의 적절한 요소를 증가시킨다.

pivot은 기준이 되는 좌표이며, 해당하는 색종이의 좌측 상단의 좌표다. 처음에는 [0, 0]이다.

이 함수는 총 세 구간으로 나눌 수 있다.

 

1. 검증 구간: 주어진 색종이 영역이 동일한 색으로 구성돼 있는지 확인한다.

검증을 시작하기 전, 해당 영역이 동일한 색으로만 구성돼 있다고 가정하며 isAccepted라는 bool 변수를 true로 지정한다. pivot 위치에 해당하는 색을 type에 저장하며, 구간 내 type과 다른 칸이 있는지 확인한다.

 

2. 색을 세는 구간: 검증을 통과했으면, 해당하는 색(type)의 수를 세어준다.

 

3. 잘게 쪼개는 구간: 검증을 통과하지 못 했으면, 4구역으로 나누어 재귀호출을 해준다.

이 구간에서 실수를 하여 시간을 많이 잡아먹었다. 인수로 받은 sides를 변형하여 그대로 사용하면 이후에 프로그램이 의도한 대로 실행되지 않는다. 그래서 새로운 배열을 선언하여 값을 지정해줬다.

새로운 pivot을 지정한 후 각 요소에 대해 재귀호출을 해준다.

 

아래는 코드 전문이다.

#include <iostream>

using namespace std;

void chop(int* pivot, int* sides, int* data, int* count) {
	// Step 1. Verification
	bool isAccepted = true;
	int type = data[pivot[1] * sides[0] + pivot[0]];
	for (int dy = 0; dy < sides[1] && isAccepted; dy++) {
		for (int dx = 0; dx < sides[1] && isAccepted; dx++) {
			int chg_x = pivot[0] + dx;
			int chg_y = pivot[1] + dy;

			if (data[chg_y * sides[0] + chg_x] != type)
				isAccepted = false;
		}
	}

	// Step 2. If it is accepted, count up.
	if (isAccepted) {
		count[type]++;
		return;
	}

	// Step 3. If it is not accepted, Chop it up
	int newSides[2] = { sides[0], sides[1] / 2 };
	int newPivots[4][2] = {	{pivot[0]					,	pivot[1]					},
								{pivot[0] + newSides[1],	pivot[1]					},
								{pivot[0]					,	pivot[1] + newSides[1]	},
								{pivot[0] + newSides[1],	pivot[1] + newSides[1]	} };
	for (auto& newPivot : newPivots)
		chop(newPivot, newSides, data, count);
}

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

	int N;
	cin >> N;

	int area = N * N;
	int* square = new int[area];
	for (int i = 0; i < area; i++)
		cin >> square[i];

	int count[2] = { 0, 0 }; // { W, B }
	int sides[2] = { N, N };
	chop(count, sides, square, count);

	for (auto& cnt : count)
		cout << cnt << "\n";

	delete[] square;
	return 0;
}