이번에는 백준 1992번 쿼드트리 문제를 풀어보았습니다.
이 문제는 흑백 영상이 주어졌을 때, 현재 영역이 모두 같은 값이면 그 값을 그대로 출력하고,
같지 않다면 4개의 정사각형으로 나누어 다시 같은 작업을 반복하는 문제입니다.
즉, 핵심은 현재 정사각형 영역이 전부 같은 값인지 확인하고,
같지 않으면 크기를 절반으로 나누어 4개의 영역을 재귀적으로 처리하는 것이었습니다.
문제 설명
N x N 크기의 흑백 영상이 주어집니다.
0은 흰 점1은 검은 점
을 의미합니다.
현재 영역이 모두 같은 값으로 이루어져 있다면 그 값 하나로 압축할 수 있고,
서로 다른 값이 섞여 있다면
- 왼쪽 위
- 오른쪽 위
- 왼쪽 아래
- 오른쪽 아래
순으로 4등분해서 다시 같은 방식으로 압축합니다.
이 과정을 반복한 최종 결과를 출력하면 됩니다.
풀이 아이디어
이 문제는 먼저 현재 영역이 모두 같은 값인지 확인하는 함수가 필요합니다.
- 모두 같다면 그 값을 출력
- 하나라도 다르면 괄호를 출력하고, 크기를 절반으로 나눠 4개의 영역을 다시 확인
하는 방식으로 구현했습니다.
즉, 한 영역을 처리하는 함수는
- 현재 정사각형이 전부 같은 수인지 확인하고
- 같으면 바로 출력
- 다르면 크기를 반으로 나누고 4개 영역을 재귀적으로 다시 처리
하는 흐름으로 동작합니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int> > bitmap;
int check_same(int y, int x, int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (bitmap[y][x] != bitmap[y+i][x+j]) {
return 0;
}
}
}
return 1;
}
void solve(int y, int x, int size) {
int half_size = size / 2;
if (!check_same(y, x, size)) {
cout << "(";
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
solve(half_size*i + y, half_size*j + x, half_size);
}
}
cout << ")";
return;
}
cout << bitmap[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++) {
string s;
cin >> s;
bitmap.push_back(vector<int>());
for (int j = 0; j < N; j++) {
bitmap[i].push_back(s[j] - '0');
}
}
solve(0,0,N);
return 0;
}풀이 흐름
- 입력받은 영상을
bitmap에 저장한다. solve(0, 0, N)으로 전체 영역부터 시작한다.- 현재
size크기의 정사각형이 모두 같은 값인지check_same()으로 확인한다. - 모두 같다면 그 값을 출력한다.
- 같지 않다면 괄호를 출력하고,
size / 2크기의 4개 영역을 차례대로 다시 확인한다. - 4개 영역 처리가 끝나면 닫는 괄호를 출력한다.
구현 포인트
1. 현재 정사각형이 모두 같은 수인지 확인
이 문제의 첫 단계는 현재 영역이 전부 같은 값인지 확인하는 것입니다.
int check_same(int y, int x, int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (bitmap[y][x] != bitmap[y+i][x+j]) {
return 0;
}
}
}
return 1;
}현재 영역의 왼쪽 위 값 bitmap[y][x]를 기준으로 잡고,
정사각형 내부의 모든 칸이 같은지 검사합니다.
- 모두 같으면
1 - 하나라도 다르면
0
을 반환하도록 했습니다.
2. 같으면 바로 출력
현재 영역이 전부 같은 값이라면 더 이상 나눌 필요가 없습니다.
cout << bitmap[y][x];즉, 압축 가능한 상태이므로 해당 값 하나만 출력하면 됩니다.
3. 다르면 4등분해서 다시 확인
같지 않다면 현재 정사각형을 다시 4개의 정사각형으로 나누어야 합니다.
int half_size = size / 2;그리고 아래처럼 2중 반복문을 사용해 4개 영역을 차례대로 재귀 호출했습니다.
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
solve(half_size*i + y, half_size*j + x, half_size);
}
}이 방식으로
(y, x)(y, x + half_size)(y + half_size, x)(y + half_size, x + half_size)
순서대로 탐색하게 됩니다.
4. 분할된 영역은 괄호로 감싸기
현재 영역이 한 번에 압축되지 않는다면 괄호로 감싸서 표현해야 합니다.
cout << "(";
...
cout << ")";즉,
- 먼저 여는 괄호 출력
- 4개 영역을 순서대로 처리
- 마지막에 닫는 괄호 출력
의 형태로 문제에서 요구하는 출력 형식을 맞췄습니다.
