백준 1992 c++ "쿼드트리" -PlusUltraCode-

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

 

 

[필자 사고]

분할정복 문제다.

처음에 문제에서 요구하는 출력값을 어떻게 보여줄지 애를 먹었었다. 

잠시 생각해보니 dfs를 이용해서 4가지 경우 를 가기전에 cout<<'(' 형식으로 해놓으면 문제를 풀 수 있었다.

여기서 조심해야 되는건 탐색 순서다. 

왼쪽상단부터 시계방향으로 DFS를 탐색해야 문제에서 요구하는 출력형태를 구할 수 있다.

 

아래는 자세한 코드해설이다.

[코드 해설]

Input() 함수

• 사용자로부터 정사각형 크기 N을 입력받고, 그 다음 줄마다 0과 1로 이루어진 문자열을 입력받아 2차원 벡터 arr에 저장합니다.
• 좌표를 1부터 사용하기 위해 arr의 크기를 (N+1) x (N+1)로 설정하고, 인덱스를 1부터 사용합니다.
• 문자열에서 각 문자를 하나씩 읽어 정수(0 또는 1)로 변환하여 arr[i][k+1]에 저장합니다.

---

DFS(left, right, size) 함수

• left와 right는 현재 영역의 시작 좌표이고, size는 정사각형 블록의 한 변의 길이입니다.
• 현재 영역이 모두 동일한 값(0 또는 1)으로 이루어져 있는지 확인합니다.
  • 만약 모두 0이면 0을 출력하고 종료.
  • 만약 모두 1이면 1을 출력하고 종료.
• 만약 다른 값이 섞여 있으면, 해당 영역을 4개의 부분으로 나누어 재귀 호출합니다. 순서는 좌상 → 우상 → 좌하 → 우하입니다.
• 출력 시 괄호 ()로 감싸며 압축 결과를 구성합니다.

---

Game_Start() 함수

• 쿼드 트리 압축을 시작하는 진입점으로, 전체 영상의 좌측 상단 좌표 (1,1)에서 크기 N의 정사각형부터 DFS()를 호출합니다.

---

main() 함수

• 전체 프로그램의 시작점.
• Input()으로 데이터를 입력받고,
• Game_Start()를 호출하여 쿼드 트리 압축 결과를 출력합니다.

[소스 코드]

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

int N;
vector<vector<int>> arr;

void Input() {
	cin >> N;
	arr.assign(N + 1, vector<int>(N + 1));

	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < N; k++) {
			arr[i][k + 1] = str[k] - '0';
		}
	}
}

void DFS(int left, int right, int size) {

	if (size == 0) {
		cout << arr[left][right];
		return;
	}
	
	bool onlyOne = true;
	bool onlyZero = true;

	int nowNumber = arr[left][right];
	if (nowNumber == 1) {
		for (int i = left; i < left + size; i++) {
			for (int k = right; k < right + size; k++) {
				if (nowNumber != arr[i][k]) {
					onlyOne = false;
				}
			}
		}

		if (onlyOne == true) {
			cout << 1;
			return;
		}
	}
	else {
		for (int i = left; i < left + size; i++) {
			for (int k = right; k < right + size; k++) {
				if (nowNumber != arr[i][k]) {
					onlyZero = false;
				}
			}
		}
		if (onlyZero == true) {
			cout << 0;
			return;
		}
	}



	cout << '(';
	DFS(left, right, size / 2);                        // 좌상
	DFS(left, right + size / 2, size / 2);             // 우상
	DFS(left + size / 2, right, size / 2);             // 좌하
	DFS(left + size / 2, right + size / 2, size / 2);  // 우하
	cout << ')';
}

void Game_Start() {
	DFS(1, 1, N);
}

int main(void) {
	Input();
	Game_Start();
}