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

 

 

문제 링크 : https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

문제

색종이 수를 세는 문제. 자세한 내용은 위의 링크를 참고.

 

 

---

접근방식

 

쿼드 트리 문제와 똑같은 문제다. base case에서 1인 경우 파란색 색종이 변수의 수를 1 증가시키고,
0인 경우에는 하얀색 색종이 변수의 수를 1증가 시키면 된다.

단, 입력에 공백이 있어서 char이 아닌 int형 배열을 이용했다.

 

코드

#include<cstdio>

int paper[128][128];
int numOfBlue = 0;
int numOfWhite = 0;

void paparCutter(int y, int x, int size)
{
	int flag = 0;
	int head = paper[y][x];

	for (int dy = 0; dy < size; dy++) {
		for (int dx = 0; dx < size; dx++) {
			if (paper[y + dy][x + dx] != head) {
				flag = 1;
				break;
			}
		}
		if (flag == 1) break;
	}

	if (flag != 1) {
		if (head == 1) numOfBlue += 1;
		else numOfWhite += 1;
		return;
	}

	else {
		int half = size / 2;
		paparCutter(y, x, half);
		paparCutter(y, x + half, half);
		paparCutter(y + half, x, half);
		paparCutter(y + half, x + half, half);

		return;
	}
}

int main()
{
	int t;
	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		for (int j = 0; j < t; j++) {
			scanf("%d", &paper[i][j]);
		}
	}

	paparCutter(0, 0, t);

	printf("%d\n%d\n", numOfWhite, numOfBlue);

	return 0;
}

 

 

다른 문제의 코드 : https://github.com/DaeeYong/Algorithm-Solution-

DaeeYong/Algorithm-Solution-