[C++] 백준 1992. 쿼드트리

🌽 문제

🥕 입출력

🥔 풀이

어제 푼 색종이 만들기의 째끔 심화 문제인 것 같다.

4등분해가는 방식은 같은데
입력이 주루룩 주어진다는 점과
나뉜 영역에 따라 괄호와 숫자 조합으로 출력해야한다는 점에서 차이가 있다.

입력은 string으로 받고, 출력할 답도 string 타입으로 선언했다.
색종이 만들 때 GPT가 추천해준 방식으로 코드를 발전시켜봤고,
4등분 전후에 앞뒤로 괄호를 붙여주어 해결했다.

실버 1이라 쫄았는데 비슷한 거 하나 풀어봤다고 원트에 성공하는 걸 보니
나 분할 정복 조금 안다고 할 수 있을지도

🥬 코드

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

int n;
vector<string> img;
string tree;

void getTree(int y, int x, int s) {
	char c = img[y][x];
	for (int i = y; i < y + s; i++) {
		for (int j = x; j < x + s; j++) {
			if (img[i][j] != c) {
				int ns = s / 2;
				tree += '(';
				getTree(y, x, ns);
				getTree(y, x + ns, ns);
				getTree(y + ns, x, ns);
				getTree(y + ns, x + ns, ns);
				tree += ')';
				return;
			}
		}
	}
	tree += c;
}

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

	cin >> n;
	img.resize(n);
	for (int i = 0; i < n; i++) cin >> img[i];
	getTree(0, 0, n);
	cout << tree;

	return 0;
}

🥜 채점