알고리즘 :: 백준 :: 1992 - 쿼드트리

 

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

• 가로/세로 길이를 나타내는 N, 1 ≤ N ≤ 64
• N개의 문자열, 0과 1로 이뤄져있음.

✏️ 문제풀이

재귀 가능성 판단하기

 

전체 흑백영상을 압축하는 과정은 4개의 부분영상 중 하나를 압축하는 과정과 같습니다.

 

위 그림을 보면 길이만 절반으로 줄어들 뿐이고,

• 범위 내에 있는 데이터가 모두 같다면 그냥 출력하고
• 하나라도 다르다면, 2, 1, 3, 4사분면 순서대로 꼭짓점 위치에서 범위를 절반으로 줄이고 다시 검사하면 됩니다.

N은 최대 64, 최대 데이터 수는 $2^{16}$으로 많지 않습니다.

 

이렇게 전체 문제와 부분 문제가 같다는 점 + 처리할 데이터가 많지 않다는 점을 파악해서 재귀로 풀 수 있어야 합니다.

 

풀이과정

시작점 `(y, x)`에서 가로, 세로로 `len`만큼 범위를 탐색할 때, 하나라도 다른 데이터를 발견한다면

(y, 			x)
(y,				x + len / 2)
(y + len / 2, 	x)
(y + len / 2, 	x + len / 2)

이렇게 4분할 한 뒤 각 시작점에 대해 재귀함수를 호출합니다.

이때, `len == 1`이라 더 이상 탐색할 범위가 없으면 그냥 `arr[y][x]`를 문자열로 변환해서 반환해주면 됩니다. 재귀함수의 기저조건이 되겠네요.

📝 코드

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

int N;
bool arr[65][65];

string solve(int sy, int sx, int len) {
	if (len == 1) return (arr[sy][sx] ? "1" : "0");
	
	string ret = "";
	bool allSame = true;
	for (int y = sy, ey = sy + len; y < ey; ++y) {
		for (int x = sx, ex = sx + len; x < ex; ++x) {
			if (arr[y][x] != arr[sy][sx]) {
				allSame = false;
				break;
			}
		}
		if (!allSame) break;
	}
	if (allSame) {
		ret += (arr[sy][sx] ? "1" : "0");
	} else {
		int newLen = len / 2;
		ret += "(";
		ret += solve(sy, sx, newLen);
		ret += solve(sy, sx + newLen, newLen);
		ret += solve(sy + newLen, sx, newLen);
		ret += solve(sy + newLen, sx + newLen, newLen);
		ret += ")";
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N;
	for (int y = 0; y < N; ++y) {
		string line;
		cin >> line;
		for (int x = 0; x < N; ++x)
			if (line[x] == '1') arr[y][x] = true;
	}
	cout << solve(0, 0, N) << '\n';
}

 

🔗 코드 링크

🕧 결과