[boj][c++] 2630 색종이만들기

2630 색종이 만들기

재귀로 풀었다. 스터디 준비하면서 dfs/bfs풀 때 비슷한 유형의 문제들을 많이 겪어봤는데 덕분에 로직은 쉽게 떠올랐다.

• x,y좌표와 한 변의 길이를 함수로 보냄
• 모든 면이 1이면 b카운트, 0이면 w카운트
• 위에 해당되지 않으면 네개의 구역을 다시 함수로 보냄
• 한 변의 길이가 1이 될 때까지 반복

이 문제의 분류에 대해 생각해봤다. 주제는 이것도 dfs로 볼 수 있는가? 이런 고민이 생기는걸 보니 내 안에서 재귀함수==dfs라는 공식이 생긴 것 같다. 한 변의 길이를 level로 생각하면 dfs인 것 같기도 하고... 근데 이걸 그래프라고 생각했을 때 한 변의 길이가 level이 될 수 있나...? 그렇게되면 풀이가 굉장히 복잡해질거같다. dfs를 사용하는 방법 중 하나가 재귀함수인거지 재귀함수가 dfs인건 아님. 그렇게 생각해보면 dfs는 아닐거같다.
+a)찾아보니까 이 문제는 dfs문제랑 결은 비슷하지만 dfs는 아니고 분할정복 문제라고 한다. 얏호
주석은 코드 수정이 필요해서 사용했다.

#include	<iostream>
using namespace std;

int arr[129][129];
int n;
int b = 0;
int w = 0;

void dfs(int x, int y, int leng)
{
	bool blue, white;
	blue = white = true;
	if (leng == 1)
	{
		if (arr[x][y] == 1)
			b++;
		else
			w++;
		return;
	}
	for (int i = x; i < x + leng; i++)
	{
		for (int j = y; j < y + leng; j++)
		{
			if (arr[i][j] == 1)
				white = false;
			if (arr[i][j] == 0)
				blue = false;
		}
	}
	if (white == true)
	{
		w++;
		//cout << "하얀색이 추가됨" << endl;
		return;
	}
	if (blue == true)
	{
		b++;
		//cout << "파란색이 추가됨" << endl;
		return;
	}
	int i = leng / 2;
	dfs(x, y, i);
	dfs(x, y + i, i);
	dfs(x + i, y, i);
	dfs(x + i, y + i, i);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];
	}
	dfs(0, 0, n);
	cout << w << "\n" << b << "\n";
	return 0;
}