백준 1992 문제풀이
in Computer Science on Algorithm
문제 링크
https://www.acmicpc.net/problem/1992
문제 설명
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 “0”이 되고, 모두 1로만 되어 있으면 압축 결과는 “1”이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고 , 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.
문제 분석
이 문제는 Divide, Conquer이라는 알고리즘의 개념을 사용해서 재귀적인 호출을 통해서 문제를 해결한다. Divide, Conquer이라는 개념을 쉽게 설명하자면 큰 문제(상위 문제)를 작은 문제(하위 문제)라는 개념으로 나누어서 작은 문제를 해결하는 목적으로 큰 문제를 해결한다. 아래에는 문제를 그림으로 나타내었다.
4개의 숫자가 주어지고 4개의 숫자가 모두 0이면 0, 1이면 1인데 1과 0이 섞여 있으면 Z를 그리며 상하좌우 탐색을 시작한다. 만약 16개의 숫자가 나온다면 4개의 구역으로 분할해서 4개의 분할된 구역을 상하좌우로 탐색한다.
코드
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
typedef long long ll;
int a[104][104];
string quard(int y, int x, int size){
if(size == 1){
return string(1,a[y][x]);
}
char b = a[y][x];
string ret = "";
bool flag = 0;
//y부터 size, x부터 size
for(int i = y; i < y + size; i++){
for(int j = x; j < x + size; j++){
if(b != a[i][j]){
ret += '(';
ret += quard(y, x, size / 2);
ret += quard(y, x + size / 2, size / 2);
ret += quard(y + size /2, x, size / 2);
ret += quard(y + size / 2, x + size / 2, size / 2);
ret += ')';
return ret;
}
}
}
return string(1,a[y][x]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++){
cin >> s;
for(int j = 0; j < n; j++){
a[i][j] = s[j];
}
}
cout << quard(0,0,n) << '\n';
return 0;
}
쿼드트리는 공간을 4개의 동일한 부분으로 나누는 방식으로 데이터를 표현하는데, 각 부분이 동일한 값을 가질 경우 더 이상 나누지 않고 하나의 값으로 표현할 수 있다. 만약 사각형의 모든 값이 같다면, 그 값을 하나의 문자로 간단히 표현할 수 있다 quard 함수는 재귀적으로 호출되며, 이 과정에서 각 사각형이 동일한 값을 갖는지 확인한다. 동일한 값을 가진 사각형은 더 이상 나누지 않고 반환하여 처리한다.