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

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

비슷한 문제: 1074(Z)
Link: https://www.acmicpc.net/problem/1074

• 조금 다른 문제지만 4분할 순서가 Z방향으로 이뤄져나가는 것을 확인하고 Z라는 문제가 생각남 -> 분할 정복 & 재귀로 유형이 비슷함.

1. 2차원 배열 탐색 방법에서 4개의 공간으로 분할됨을 확인 -> Divide&Conquer 문제로 예상
2. 공간을 줄여나가며 분할을 반복적으로 시도 -> Recursion으로 해결해야 될 것으로 예상

1번 풀이

#include<iostream>
#include<vector>
#define HALF tileSize / 2
#define V vector<string>
using namespace std;
int n;

void input(V& board) {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		board.push_back(s);
	}
}

void rec(V board, int x, int y, int tileSize) {
	char cur = board[x][y];
	for (int i = x; i < x + tileSize; ++i) {
		for (int j = y; j < y + tileSize; ++j) {
			if (board[i][j] == cur) continue;
			cout << '(';
			rec(board, x, y, HALF);
			rec(board, x, y + HALF, HALF);
			rec(board, x + HALF, y, HALF);
			rec(board, x + HALF, y + HALF, HALF);
			cout << ')';
			return;
		}
	}
	cout << cur;
}

void solution(V board) {
	rec(board, 0, 0, n);
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	V board;
	input(board);
	solution(board);
	return 0;
}

2번 풀이

#include<iostream>
using namespace std;
#define HALF tileSize / 2
#define MAX 1 << 6

int n;
char board[MAX][MAX];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < s.length(); ++j) {
			board[i][j] = s[j];
		}
	}
}

void rec(int x, int y, int tileSize) {
	char cur = board[x][y];
	for (int i = x; i < x + tileSize; ++i) {
		for (int j = y; j < y + tileSize; ++j) {
			if (board[i][j] == cur) continue;
			cout << '(';
			rec(x, y, HALF);
			rec(x, y + HALF, HALF);
			rec(x + HALF, y, HALF);
			rec(x + HALF, y + HALF, HALF);
			cout << ')';
			return;
		}
	}
	cout << cur;
}

void solution() {
	rec(0, 0, n);
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	input();
	solution();
	return 0;
}

2번 풀이는 상대적으로 2차원 배열의 용량이 적어 직접 선언하고 풀이함.
배열크기가 충분히 제어될 만큼 작은 경우 벡터보다는 배열을 선언하는 것을 추천합니다.(물론 상황에 따라 다릅니다.)