백준 1992 - 쿼드트리(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

재귀를 사용하는 문제였습니다.

문제 조건

출력 예시

답이 나오는 과정입니다.

1. map을 한번 확인해본다

  1-1. map이 0이나 1로만 모두 차있다면 해당 값을 출력합니다.

  1-2. 위의 경우가 아니라면 map을 4개로 나눈뒤 (를 출력합니다.

2. 4개로 나뉜 map을 다시 확인해봅니다.

3. 1~2과정을 반복한뒤, 확인이 끝날때마다 )을 출력합니다.

 

1. map을 확인하는 과정

void divide(int num, int x, int y) {
	if (num == 1) {
		ans += map[x][y];
	}
	else {
		bool zero = true, one = true;
		for (int i = x; i < x + num; i++) {
			for (int j = y; j < y + num; j++) {
				if (map[i][j] == '1') {
					zero = false;
				}
				else {
					one = false;
				}
			}
		}
		if (zero) {
			ans += '0';
		}
		else if (one) {
			ans += '1';
		}
		else {
			ans += '(';
			divide(num / 2, x, y);
			divide(num / 2, x, y + num / 2);
			divide(num / 2, x + num / 2, y);
			divide(num / 2, x + num / 2, y + num / 2);
			ans += ')';
		}
	}
}

num이 1이라는 의미는 한칸씩 확인한다는 것임으로 해당하는 map의 값을 저장합니다.

 

num이 1이 아닐경우에는 num*num 크기의 map을 확인한뒤, 해당 칸들이 어떤 수로 차있는지를 확인합니다.

같은 수로 차있지 않다면 4개로 나눈뒤 다시 확인해줍니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

char map[65][65];
int N;
string ans;

void divide(int num, int x, int y) {
	if (num == 1) {
		ans += map[x][y];
	}
	else {
		bool zero = true, one = true;
		for (int i = x; i < x + num; i++) {
			for (int j = y; j < y + num; j++) {
				if (map[i][j] == '1') {
					zero = false;
				}
				else {
					one = false;
				}
			}
		}
		if (zero) {
			ans += '0';
		}
		else if (one) {
			ans += '1';
		}
		else {
			ans += '(';
			divide(num / 2, x, y);
			divide(num / 2, x, y + num / 2);
			divide(num / 2, x + num / 2, y);
			divide(num / 2, x + num / 2, y + num / 2);
			ans += ')';
		}
	}
}

void solve() {
	divide(N, 1, 1);
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!