1992 - 쿼드트리

• 난이도: 실버 1
• 날짜: 2023년 3월 11일
• 상태: Correct
• 추가 검토 여부: No
• 알고리즘 : 분할 정복, 재귀

Solution

• compressable함수를 구현하여 2차원 배열의 모든 원소가 같은 원소로 구성되어있는지 확인한다.
  • 하나라도 다른 원소가 포함되어 있다면 false를 반환한다.
• compress함수를 구현하여 recursion을 통해 입력된 배열에 대해 compress를 수행한다.
  • 만약 모든 원소의 값이 같지 않아서 압축이 되지 않을 경우, 4분할을 통해 compress함수를 재귀호출한다(recursion)
  • 처음에는 이차원 배열을 새롭게 생성하여 compress를 호출하였으나, compressable과 compress함수의 인자로 row, col의 시작 인덱스를 주어, 추가 배열 생성 없이 호출이 가능하도록 구현했다.
• 메인 함수에서 입력을 받을 때 입력 형식을 맞추기 위해 char타입으로 입력을 받아 하나씩 저장했다.
  • int타입으로 구현하면 0과 1이 붙어서 한 숫자로 인식된다.
• 처음에 이차원 배열의 동적할당 후 생성하는 문법에 오류가 있어 문제를 몇 번 틀렸다.
  • 이중 포인터 하나만 배열로 동적할당 한 뒤, 각 이중 포인터 배열의 원소에 대해 다시 동적할당하는 방식으로 코딩해야 한다.

code

#include <iostream>
using namespace std;

bool compressable(int ** arr, int row, int col, int size)
{
	int elem = arr[row][col];
	for(int i = row; i < row+size; i++)
	{
		for(int j = col; j < col+size; j++)
		if(arr[i][j] != elem) return false;
	}
	return true;
}

void compress(int ** arr, int row, int col, int size)
{
	if(compressable(arr, row, col, size)) cout << arr[row][col];
	else
	{
		cout << "(";
		int sub_size = size / 2;
		compress(arr, row, col, sub_size);
		compress(arr, row, col+sub_size, sub_size);
		compress(arr, row+sub_size, col, sub_size);
		compress(arr, row+sub_size, col+sub_size, sub_size);
		cout << ")";
	}
} 

int main()
{
	int N;
	cin >> N;
	int ** arr = new int*[N];
	for(int i = 0; i < N; i++)
	{
		arr[i] = new int[N];
		for(int j = 0; j < N; j++)
		{
			char c;
			cin >> c;
			arr[i][j] = c - '0';
		}
	}
	compress(arr, 0, 0, N); 
	return 0;
}

ref

1992번: 쿼드트리