백준 1992 쿼드트리 사진압축[C++]
<Input>
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
<Output>
영상을 압축한 결과를 출력한다.
예제입력 1.
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011예제출력 1.
((110(0101))(0010)1(0001))백준 1992 : 쿼드트리 바로 가기
https://www.acmicpc.net/problem/1992
<Hint>
이 문제는 분할정복('Divide and Conquer')문제이다.
보통 분할 정복 문제는 재귀함수를 이용하는데, 원하는 조건을 만족시키지 않으면, 다시 문제를
분할(Divide) 하여 문제를 풀게 된다. / 참고: 백준 2630[색종이 만들기]
<Solution>
1. n과 arr[70][70]을 입력으로 받는다. //MAX =70으로 설정해주었음.
2. 분할 정복을 위한 재귀 함수로, 4등분의 기준이 될 size (x,y)와 크기 n을 넘겨준다.
3. arr[x][y]가 1일 때의 갯수를 체크한다.
4. 갯수가 0이면(=전체 흰색) 흰색++, 갯수가 N^2개면(=전체 파란색) 파란색++
5. 전체가 "1"도 "0"도 둘 다 아니면, 분할하여 4개의 부분문제를 해결한다.
- N^2을 (N/2)^2 * 4의 부문제 4개로 분할하며 재귀시킨다.
//재귀 시킬시, 각 재귀를 감싸주는 "("와 ")"를 삽입시켜서 depth를 해결시킨다.
- 왼쪽 위의 기준점 (x, y)와 N/2로 재귀
- 오른쪽 위의 기준점 (x, y+N/2)와 분할한 N/2로 재귀
- 왼쪽 아래의 기준점 (x+N/2, y)와 분할한 N/2로 재귀
- 오른쪽 아래의 기준점 (x+N/2, y+N/2)와 분할한 N/2로 재귀
// 간단히 생각하면 그냥 계속 4등분 해줘서 재귀함수를 돌려준다 생각하면 된다...
6. "0"의 개수와 "1"을 감싸는 cout << 출력
<CODE>
#include <iostream>
#include <string>
using namespace std;
int N;
int arr[70][70];
void check(int startX, int startY, int endX, int endY);
void input(){ // 2630번 문제와 다르게 띄어쓰기가 없어 input()함수를 받았습니다..
cin >> N;
for(int i=0;i<N;i++){
string S; cin>>S;
for(int j=0;j<S.length();j++){
arr[i][j] = S[j]-'0';
}
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(0);
input();
check(0, 0, N-1, N-1); // 2630 과 다르게 0,N-1 로 시작!
return 0;
}
void check(int startX, int startY, int endX, int endY) {
int start = arr[startY][startX];
int size = (endX - startX + 1) / 2;
for (int i = startY; i <= endY; i++) {
for (int j = startX; j <= endX; j++) {
if (start != arr[i][j]) {
cout<<"(";
check(startX, startY, endX - size, endY - size);
check(startX + size, startY, endX, endY - size);
check(startX, startY + size, endX - size, endY);
check(startX + size, startY + size, endX, endY);
cout<<")";
return;
}
}
}
if (start == 0)
cout << "0";
else
cout << "1";
}
Uploaded by Notion2Tistory v1.1.0