쿼드트리
https://www.acmicpc.net/problem/1992
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 37409 | 22836 | 17917 | 61.630% |
문제
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
출력
영상을 압축한 결과를 출력한다.
예제 입력 1
8 11110000 11110000 00011100 00011100 11110000 11110000 11110011 11110011
예제 출력 1
((110(0101))(0010)1(0001))
출처
- 데이터를 추가한 사람: kofgb
알고리즘 분류
통과된 코드
분할정복 알고리즘을 이용하여 문제를 해결하였다.
일단 해당 구역의 모든 값이 같은지 확인한다.
다르다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
이렇게 4개의 영상으로 나누어서 다시 확인한다. (분할 정복)
#include <iostream>
using namespace std;
int N;
char map[64][64];
string result;
void DivisionalConquest(int x, int y, int w)
{
bool check = true;
for (int i = 0; i < w ; i++) {
for (int j = 0; j < w; j++) {
if (map[x][y] != map[x + i][y + j]) check = false;
}
if (!check) break;
}
if (check) {
result.push_back(map[x][y]);
return;
}
else if (w == 1) {
for (int i = 0; i < w; i++) {
for (int j = 0; j < w; j++) {
result.push_back(map[x + i][y + j]);
}
}
return;
}
result.push_back('(');
DivisionalConquest(x , y, w / 2);
DivisionalConquest(x , y + w / 2, w / 2);
DivisionalConquest(x + w / 2, y, w / 2);
DivisionalConquest(x + w / 2, y + w / 2, w / 2);
result.push_back(')');
}
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
std::cout.tie(NULL);
cin >> N;
string str;
for (int i = 0; i < N; i++) {
cin >> str;
for (int j = 0; j < str.length(); j++) {
map[i][j] = str[j];
}
}
DivisionalConquest(0, 0, N);
cout << result;
return 0;
}
추가 반례
https://www.acmicpc.net/board/view/110169
예제 입력 A
8 11110000 11110000 00011100 00011100 11110000 11110000 11110011 11110011
예제 출력 A
((110(0101))(0010)1(0001))
예제 입력 B
16 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000 1111000011110000
예제 출력 B
((1010)(1010)(1010)(1010))
예제 입력 C
32 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000 11110000111100001111000011110000
예제 출력 C
(((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010)))
예제 입력 D
64 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000 1111000011110000111100001111000011110000111100001111000011110000
예제 출력 D
((((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010)))(((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010)))(((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010)))(((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))((1010)(1010)(1010)(1010))))
예제 입력 E
1
예제 출력 E
1
![백준 11057번 (오르막 수, C++, DP) / 추가 반례 [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og-1.png)
![백준 11562번 (백양로 브레이크, C++, Floyd-Warshall) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og.png)