<< 문제 >>
https://www.acmicpc.net/problem/1992
쿼드트리는 영상이나 이미지 압축에 주로 사용되는 알고리즘입니다.
4분면으로 나누어 흑/백을 판단하고 섞여있다면 다시 4분면으로 나누어 판단합니다.
듣기만 해도 재귀함수 생각이 절로나죠?
<< 코드 >>
#include <cstdio>
#include <string>
using namespace std;
int table[64][64];
void quadTree(int num, int y, int x){
if (num == 1) { // 크기가 1인 경우는 바로 return
printf("%d", table[y][x]);
return;
}
// 같은 색으로 이루어져있는지 확인
bool isWhite = false;
bool isBlack = false;
bool isClear = true;
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
if (table[y + i][x + j] == 0) {
isWhite = true;
}
else {
isBlack = true;
}
}
}
if (isWhite && isBlack) { // 둘 다 true라는건 섞였다는 뜻
isClear = false;
}
if (!isClear) { // 하나로만 이루어지지 않은 경우
printf("%c", '(');
quadTree(num / 2, y, x);
quadTree(num / 2, y, x + num / 2);
quadTree(num / 2, y + num / 2, x);
quadTree(num / 2, y + num / 2, x + num / 2);
printf("%c", ')');
}
else if (isWhite && !isBlack) { // 화이트만 있는 경우
printf("%d",0);
}
else if (isBlack && !isWhite) { // 블랙만 있는 경우
printf("%d", 1);
}
}
int main() {
int num;
scanf("%d", &num);
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
scanf("%1d", &table[i][j]);
}
}
quadTree(num, 0, 0);
}
<< 깃헙 >>
< 백준 BaekJoon : 1715번 카드 정렬하기 > C++ (0) | 2024.03.30 |
---|---|
< 백준 BaekJoon : 1927번 최소 > C++ (0) | 2024.03.15 |
< 백준 BaekJoon : 9251번 LCS > C++ (0) | 2024.01.31 |
< 백준 BaekJoon : 11053번 가장 긴 증가하는 부분 수열 > C++ (0) | 2024.01.30 |
< 백준 BaekJoon : 2156번 포도주 시식 > C++ (0) | 2024.01.29 |
댓글 영역