https://www.acmicpc.net/problem/1992
문제
> 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
접근
색종이 나누기 문제와 비슷한 방식으로 접근한다.
재귀를 통해 분할정복을 한다.
Quad메소드에서 시작으로 들어온 행, 열 값을 통해 그 위치에 있는 1또는 0을 잡고 입력으로 들어온 범위의 배열안이 모두 같은지 탐색한다. 만약 다른게 발견되면 바로 이중 반복을 깨고 나와
탐색 구역을 4등분해준다. 각각의 등분에 입력받았던 행과 열의 값을 더해 시작 위치를 각각 지정해준다.
만약 배열안이 모두 같았다면 이중반복문이 끝나고 안이 0이었는지 1이었는지 기준으로 잡았던 값을 출력해준다.
괄호의 위치는 메소드안의 재귀 반복문의 i는 0일 때, 즉 시작일 때 ( 여는괄호를 출력해주고 4등분이 끝난 2중반복문의 밖에 )닫는괄호를 출력해준다.
문제해결
> Quad의 입력으로 영상의 시작점과 크기가 주어진다.
이를 기반으로 시작점의 값을 기준으로 잡아 이중반복으로 영상의 전체를 탐색한다.
> 다른게 존재하지 않으면 valid 부울값이 변하지 않아 그대로 이중반복이 끝나 tmp를 출력하고 함수가 깨진다.
> 다른게 있다면 valid에 걸려 이중반복이 깨지고 아래의 4등분하는 재귀로 들어간다.
> 여기서 조각이 나눠졌다를 표현하기 위해 시작지점에 여는괄호( 를 출력하고 4등분한 각각의 시작점에 입력받은 행과 열을 더해 진짜 시작점을 계산해 재귀한다.
> 각각의 재귀가 모두 끝나 반복문이 끝나면 해당 조각에 대한 연산이끝났으므로 닫는괄호 )를 출력해준다.
> main함수에서 영상을 저장할 벡터를 문자형으로 주고
한줄 씩 문자열로 받아 이를 문자로 쪼개 영상을 만들어준다.
> 앞에서 정의한 Quad메소드에 시작점 0,0과 입력받은 사이즈 N을 넣어 호출해 출력한다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int N;
vector<vector<char>> quad;
void Quad(int row, int col, int size)
{
char tmp = quad[row][col];
bool valid = false;
for (int i = row; i < row + size; i++)
{
for (int j = col; j < col + size; j++)
{
if (tmp != quad[i][j])
{
valid = true;
break;
}
}
if (valid) break;
}
if (!valid)
{
cout << tmp;
return;
}
for (int i = 0; i < 2; i++)
{
if (i == 0) cout << "(";
for (int j = 0; j < 2; j++)
{
Quad(i * (size / 2) + row, j * (size / 2) + col, size / 2);
}
}
cout << ")";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
quad.resize(N, vector<char>(N));
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
for (int j = 0; j < N; j++)
{
quad[i][j] = str[j];
}
}
Quad(0, 0, N);
}
후기
오류가 딱 세가지였다. 1. 입력이 끝나지 않는오류
처음에 int형으로 벡터 quad를 선언해 받았다. 아무리 제대로 입력해도 끝나지 않아 계속 노려보니 내가 한줄씩 통으로 입력하고있었다.
이걸 하나씩 끊어서 입력하면 문제에서 주어진 영상대로가 아니므로 문자형 벡터로 바꿔 문자열로 한줄씩 받아 이를 쪼개 저장해 해결했다.
2. 괄호의 위치가 이상함
처음에 main함수에 함수 호출부분 Quad앞뒤로 (와 )를 출력했다.
이렇게 되면 문제나 예제의 답을 넣었을 때 겉에 (와 )가 한 겹 더있는 식으로 나온다.
생각해보면 재귀에 ()를 출력해주는걸 넣었기 때문에 제일 밖의 괄호들을 생각해 main에서 이를 주면 영상의 모든 값이 같아서 결과가 0이나 1이 나오는 경우빼곤 옳지않은 괄호가 나온다.
3. 수가 중복돼서 나온다.
처음에 값이 모두같아 valid가 변하지않았을 때, cout << tmp를 첫 for문의 끝부분에 넣었다. 이렇게 되면 i의 값이 변할 때마다 tmp를 찍어주는 것이므로 이상하게 나오는것이다. 그래서 이를
반복문 밖으로 빼고, 영상의 값이 다를 때는 출력이 되면 안되므로
valid가 false일때만 출력하고 return으로 끝내도록하여 정답을 맞추었다.
