[백준/BOJ] 1992번 쿼드트리 (C/C++)

 

백준 온라인 저지(BOJ) 1992번 쿼드트리

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

1992번: 쿼드트리

* 사용언어 : C언어, C++

 

1. 풀이

일정 크기의 정사각형에 모두 0, 1 인 경우 숫자 하나로 표현하고,

각 성분이 추가로 세분화되면 해당 정사각형을 () 로 묶어서 출력

 

2. 풀이

분할 정복의 기초적인 문제입니다.

재귀 함수는 ① 종료 조건, ② 처리, ③ 재귀 호출 3단계로 작성하게 됩니다.

 

저는 재귀 함수 문제를 풀 때면 ①번, ③번은 나중에 생각하고,

일단 ②번(이 함수가 무슨 역할을 하는지)을 먼저 정의하고 구현을 시작합니다.

이 문제의 경우 원하는 좌표 내 모든 값이 같은 수 인지를 확인하는 함수를 작성해야합니다.

 

이를 처리하기 위해 정사각형의 좌상단 값을 fv(first value)로 저장한 뒤

정사각형 내부를 탐색하면서 다른 값이 있는지를 탐색했습니다.

 

다른 값이 없으면(즉, 모두 같으면) 그대로 그 숫자를 출력했고,

다른 값이 있으면 즉시 반복문을 탈출하게 한 뒤 [괄호 출력] 과 [4등분 재귀 호출]을 했습니다.

(문제의 탐색 방향(좌상, 우상, 좌하, 우하)에 맞게 순서를 배치해야합니다)

 

크기를 줄여가며 탐색하는 형태의 재귀 함수에서 ① 종료 조건은

n이 0이면 return 하는 형태로 작성하는 경우가 일반적입니다.

하지만 이 문제는 n이 1일 때 알아서 종료되기 때문에 따로 작성하지 않았습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>

const int LM = 64;
int map[LM][LM];

void compress(int sy, int sx, int n) {
	int fv = map[sy][sx];
	int valid = 1;
	for (int y = sy; y < sy + n; ++y) {
		for (int x = sx; x < sx + n; ++x) {
			if (fv != map[y][x]) {
				valid = 0;
				break;
			}
		}
		if (valid == 0) break;
	}

	if (valid == 1) {
		printf("%d", fv);
	}
	else {
		printf("(");
		compress(sy, sx, n / 2);
		compress(sy, sx + n / 2, n / 2);
		compress(sy + n / 2, sx, n / 2);
		compress(sy + n / 2, sx + n / 2, n / 2);
		printf(")");
	}
}

int main(){
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n;
	char c;
	scanf("%d ", &n);
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < n; ++x) {
			scanf("%c ", &c);
			map[y][x] = c - '0';
		}

	}
	compress(0, 0, n);
	return 0;
}