개요
백준 문제 1992번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 60분
https://www.acmicpc.net/problem/1992
문제
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며,
이 영상을 쿼드 트리 구조를 이용하여 압축하면 “(0(0011)(0(0111)01)1)”로 표현된다.
N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <iostream>
#include <string>
using namespace std;
const int MAX = 64;
int input[MAX][MAX];
string tmp = "";
bool allPixelSame(int startRow,int startCal,int divUnit)
{
int comparePixel = input[startRow][startCal];
for(int i=0;i<divUnit;i++)
{
for(int j=0;j<divUnit;j++)
{
if(input[startRow+i][startCal+j] != comparePixel)
{
return false;
}
}
}
return true;
}
void quadTree(int startRow,int startCal,int divUnit)
{
if(divUnit == 1 || allPixelSame(startRow,startCal,divUnit))
{
tmp.append(to_string(input[startRow][startCal]));
}
else
{
tmp.append("(");
for(int i=0;i<divUnit;i+= divUnit/2)
{
for(int j=0;j<divUnit;j+=divUnit/2)
{
quadTree(startRow+i,startCal+j,divUnit/2);
}
}
tmp.append(")");
}
}
void solve()
{
int N;
char tmpInput;
cin >> N;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin >> tmpInput;
input[i][j] = tmpInput - '0';
}
}
quadTree(0,0,N);
cout << tmp;
}
int main()
{
solve();
}
|
풀이
전형적인 분할정복 문제이며 이전에 풀었던 문제와 유사한 유형이어서 쉽게 풀 수 있었음.
배울 점, 메모