[백준] 2630번: 색종이 만들기 C++로 풀어보기

2630번 설명

생각

재귀를 사용하면 될 것 같다.

1. 사각형을 4분면으로 나눠서 거기서부터 루프를 돌면서 0인지 1인지 확인한다.

2. bool 변수를 두개 만든다. 하나는 루프를 돌 때 한 번이라도 1이 나오면 false(흰색 사각형이 아니라는 뜻), 또 하나는 루프를 돌 때 한 번이라도 0이 아니면 false(파란색 사각형이 아니라는 뜻.)이다.

3. 그리고 재귀를 사용해서 흰색 혹은 파란색 사각형을 찾을 때까지 계속 탐색한다.

4. 두 bool 변수 중 하나라도 true가 나오면 사각형을 찾은 것이므로 재귀를 그만둔다.

5. 파란색 사각형이면 파란색 사각형의 개수를 나타내는 변수에 1을 더하고, 흰색 사각형이면 흰색 사각형의 개수를 나타내는 변수에 1을 더한다.

6. 모든 과정이 다 끝나면 하얀색 색종이의 개수와 파란색 색종이의 개수를 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
int bluecnt = 0;
int whitecnt = 0;

vector <vector<int>> v; // 벡터 선언

void find(int x, int y, int n) {
	bool blue = true; // 파란색 사각형인지 나타내는 bool 변수
	bool white = true; // 흰색 사각형인지 나타내는 bool 변수

	
	for (int i = x; i < x+n; i++) {
		for (int j = y; j < y+n; j++) {
			if (v[i][j] != 1) { // 1을 나타내지 않는다면
				blue = false; // 파란색 사각형이 아니다
			}
			else {
				white = false; // 1을 나타낸다면 흰색 사각형이 아니다.
			}
		}
	}

	if (blue == true) { // 파란색 사각형이면
		bluecnt++; // bluecnt에 1을 더한다.
		return;
	}
	else if (white == true) { // 하얀색 사각형이면
		whitecnt++; // whitecnt에 1을 더한다.
		return;
	}
	
	if (n > 1) { // 아직 사각형이 나타나지 않았으면 재귀를 돌린다.
		find(x, y, n / 2);
		find(x, y + n / 2, n / 2);
		find(x + n / 2, y, n / 2);
		find(x + n / 2, y + n / 2, n / 2);
	}
	else {
		return;
	}
	

}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin >> n;

	// vector<vector <int>> v(n, vector<int>(n, 0)); <- 이렇게 하면 틀린다..
	v = vector<vector<int>>(n, vector<int>(n, 0)); // 벡터 0으로 초기화

	for (int i = 0; i < n; i++) { // 숫자 입력
		for (int j = 0; j < n; j++) {
			int x;
			cin >> x;
			v[i][j] = x;
		}
	}

	bluecnt = 0;
	whitecnt = 0;
	
	find(0, 0, n); 

	cout << whitecnt << "\n"; // 출력
	cout << bluecnt;
	
}

 

결과

2630번 결과

벡터를 2차원으로 만드는 것이 익숙하지 않아서 살짝 애를 먹었다. 익숙해지자.

그리고 재귀도 많이 써봐야겠다.