문제
문제설명
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
출력
영상을 압축한 결과를 출력한다.
해결방법
문제분석
영상이 배열과 같이 숫자로 주어지는데 해당배열이 모두 0또는 1로 되어있으면 0또는 1로 압축을 진행한다. 그렇지않으면 배열을 4개로 나누어 다시 압축을 진행하는 문제이다.
풀이
우선 배열의 입력을 받은 후에 재귀를 사용하여 압축을 진행하면 될 것 같았다.
그래서 압축을 하는 함수인 sol함수를 만들었고 매개변수로 배열과 n의값 압축을 하는 영역의 좌상단의 좌표를 받도록 해주었다.
먼저 배열 좌상단의 값을 저장하여 배열내의 값들과 비교하고 모두동일하다면 저장한 값을 반환하고 다르다면 재귀를 이용하여 4개의 영역으로 나눈뒤에 다시 압축을 진행하도록 구현하여 주었다.
코드
#include<iostream>
#include<string>
#include <vector>
struct xy{
int x;
int y;
};
using namespace std;
string sol(string arr[], int n, xy start)
{
int x = start.x;
int y = start.y;
bool flag = true;
char c;
string ans;
for (int i = x; i < x + n; i++)
for (int j = y; j < y + n; j++)
if (i == x && j == y) c = arr[i][j];
else if (arr[i][j] != c) {
flag = false;
break;
}
if (flag == true) ans = c;
else {
ans = "(";
int dx[4] = { 0,0,n / 2,n / 2 };
int dy[4] = { 0,n / 2,0,n / 2 };
for (int i = 0; i < 4; i++)
{
ans += sol(arr, n / 2, { start.x + dx[i],start.y + dy[i] });
}
ans += ")";
}
return ans;
}
int main()
{
int n;
cin >> n;
string s;
string *arr = new string[n];
for (int i = 0; i < n; i++) {
cin >> s;
arr[i] = s;
}
xy xy = { 0,0 };
cout<<sol(arr, n, xy);
}
후기
압축하는 부분에서 영역을 나눌때 헷갈리긴했지만 그부분 제외하면 그리 어렵지 않은 문제였다.
그리고 원래 입력을 배열형태로 저장해야하면서 크기가 정해지지 않은경우에는 대부분 벡터를 사용했었는데 저번에 문제풀다가 배열이 속도가 훨빠른것을 확인하였기에 new를 사용하여 보았는데 이 문제처럼 배열의 크기가 변하지 않는 경우에서는 배열을 new를 이용하여 동적할당을 사용하는 것이 좋아보인다.
사용한 문법
new : C언어에서 동적할당을 할때 사용하였던 malloc을 대신하여 동적할당이 가능하다.
+해제에 사용했던 free는 delete를 이용하여 대채가 가능하다.
int* a = new int(5);//힐딩후 초기화
delete a; //해제
int* arr = new int[5]; //1차원 배열 할당
//int* arr = new int[5]{};//0으로 초기화
delete[] arr; //해제
int **arr=new int*[5]; //2차원 배열할당
for(int i=0;i<5;i++)
arr[i]=new int[5];
for(int i=0;i<5;i++) //해제
delete[] arr[i];
delete[] arr;위와 같은 방식을 사용하여 동적할당, 해제를 사용할 수 있다.
