[1992] 쿼드트리

---

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

1992번: 쿼드트리

 

분할 정복 문제이다.

왜 정수 입력이 안되지 의문이었는데, 띄어쓰기가 안 돼있는 걸 인식하지 못했었다. ㅋ

그래서 string으로 한 줄 받고 parsing 해주며 입력 부분을 처리했다.

 

 

그 다음 중요한 건 괄호 처리! 

입력 순서는 아래와 같은 것을 확인했다.

이걸 참고해서 예제 1을 검사해보면

이렇게 된다.

영역이 시작할 때 괄호가 열려야 하고, 영역이 끝나면 괄호가 닫혀야 한다. 

이것을 어떻게 구현할까 고민을 좀 했는데 분할 정복 코드 위/아래에 괄호를 넣어주는 것으로 해결했다.

또한 재귀 함수를 호출할 때 한 변의 길이가 2를 나눈 것만큼 감소하므로 n=n/2하여 넣어주었다.

cout << "("; // 시작 부분에 "(" 삽입
f(r, c, n); // 1영역
f(r, c + n, n); // 2영역
f(r + n, c, n); // 3영역
f(r + n, c + n, n); // 4영역
cout << ")"; // 끝 부분에 ")" 삽입

 

 

전체 코드는 아래와 같다.

#include <iostream>
#include <string>
using namespace std;

int N;
int A[65][65];

void f(int r, int c, int n) {
	int flag = A[r][c]; bool isCorrect = true;	
	for (int i = r; i <= r + n - 1; i++) {
		for (int j = c; j <= c + n - 1; j++) {
			if (A[i][j] != flag) { // 영상이 모두 같은 숫자가 아니라면
				isCorrect = false;
				break;
			}
		}
		if (!isCorrect) break;
	}

	if (isCorrect) {
		// 주어진 영상의 번호가 다 일치하는 경우
		cout << flag;
	}
	else {
		// 쪼개야되는 경우
		n /= 2;
		cout << "("; // 시작 부분에 "(" 삽입
		f(r, c, n); // 1영역
		f(r, c + n, n); // 2영역
		f(r + n, c, n); // 3영역
		f(r + n, c + n, n); // 4영역
		cout << ")"; // 끝 부분에 ")" 삽입
	}
}

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

	cin >> N;

	for (int i = 1; i <= N; i++) {
		string x;
		cin >> x;
		// 문자열 자르기
		for (int k = 1; k <= N; k++) {
			A[i][k] = x[k - 1] - '0'; // 숫자로 변환
		}
	}

	f(1, 1, N);
}