백준 1992번 - 쿼드트리

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

1992번: 쿼드트리

 

풀이 과정

 전체 map 탐색하며 조건을 만족하면 출력, 아니라면 만족할 때까지 분할하는 문제이다. 입력을 받고 qt()라는 재귀 함수를 작성해서 문제를 풀었다. qt() 함수는 먼저 지정된 영역 (x, y) 부터 (x + nn, y + nn)까지 값이 동일한지 검사한다. 동일하다면 범위 내 mp 요소를 하나 출력한다. 그러나 동일하지 않다면 mp를 4부분으로 분할해서 다시 검사한다. 분할 될 때는 앞에 '(', 분할 된 모든 qt()가 종료되면 ')'를 출력한다.

 

 느낀 점

 처음 풀 때는 어려움을 많이 느꼈는데, 다시 풀어보니 간단히 풀렸다. 분할 정복이란 무엇인지 직관적으로 느낄 수 있었다. 중간에 qt()를 4부분으로 분할할 때 y와 x를 하나 헷갈려 바꾸어 적었고, 디버깅하면서 탐색 범위를 좁히고 수정했다.

 

#include<bits/stdc++.h>
using namespace std;

int n;
char mp[65][65];

void qt(int y, int x, int nn) {
	int flag = false, _prev = mp[y][x];
	for (int i = y; i < y + nn; i++) {
		for (int j = x; j < x + nn; j++) {
			if (mp[i][j] != _prev) flag = true;
		}
	}
	//값이 동일하지 않다면 분할
	if (flag) {
		cout << "(";
		qt(y, x, nn / 2);
		qt(y, x + nn / 2, nn / 2);
		qt(y + nn / 2, x, nn / 2);
		qt(y + (nn / 2), x + (nn / 2), nn / 2);
		cout << ")";
	}//동일하면 출력
	else cout << mp[y][x];

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//입력
	cin >> n;
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < n; j++) {
			cin >> mp[i][j];
		}
	}
	//수행 및 출력
	qt(0, 0, n);

	return 0;
}