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

문제

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

 

 분석

 색이 같지 않은 경우 N/2으로 나눌때, 기존 N*N 종이에 4 구역으로 나뉜다.

그러므로 4 구역으로 분할해서 풀면 된다.

기저 사례는 구역내 색이 같을 때 이다.

 

 구현

int w = 0, b = 0;

bool decidePaper(const vector<vector<int>>& input_data, int y, int x, int N)
{
	int sum = 0;
	for (int i = y; i < y + N; i++)
	{
		for (int j = x; j < x + N; j++)
		{
			sum += input_data[i][j];
		}
	}
	//0인 경우 흰색, N*N인 경우 파랑색
	if (sum == 0 || sum == N * N) return true;
	else return false;
}

void makeQuardTree(const vector<vector<int>>& input_data, int y, int x, int N)
{
	//base case : 다 같은 경우
	if (decidePaper(input_data, y, x, N))
	{
		if (input_data[y][x] == 1) b++;
		else w++;
		return;
	}
	makeQuardTree(input_data, y, x, N / 2); //좌상단
	makeQuardTree(input_data, y, x + N / 2, N / 2); //우상단
	makeQuardTree(input_data, y + N / 2, x, N / 2); //좌하단
	makeQuardTree(input_data, y + N / 2, x + N / 2, N / 2); //우하단
}

int main()
{
	int N;
	cin >> N;
	vector<vector<int>> input_data;
	for (int i = 0; i < N; i++)
	{
		vector<int> a(N);
		input_data.push_back(a);
	}
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			cin >> input_data[y][x];
		}
	}
	
	makeQuardTree(input_data, 0, 0, N);
	cout << w << '\n' << b;
	return 0;
}

 

 회고

 종만북에서 이와 비슷한 문제를 푼 경험이 있다면 쉽게 풀 수 있는 문제다.

 

2020/11/16 - [알고리즘 문제 해결 전략] - 분할 정복 - 1. 쿼드 트리 뒤집기

분할 정복 - 1. 쿼드 트리 뒤집기