#문제
https://www.acmicpc.net/problem/1992
#작성 코드
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
|
#include <iostream>
#include <cstdio>
using namespace std;
int n; // max 64
int video[65][65];
void compress(int x, int y, int size){
// 해당범위의 첫 값을 저장
int first = video[x][y];
bool same = true;
// size가 1이라면 무조건 출력한다.(더이상 분할할수없으므로)
if( size==1 ){
cout<<first;
return;
}
// 범위 내 값을 첫 값과 비교하며 같지 않다면 same을 false로 바꾼다
for(int i=x; i<x+size; i++){
for(int j=y; j<y+size; j++){
if( first != video[i][j] ){
same = false;
}
}
}
// 범위 내 모든 값이 같다면 첫 값을 출력하고 함수 종료
if( same ){
cout<<first;
return;
}
// 범위 내 값이 모두 같지 않다면 4분할하여 비교한다.
else{
cout<<"(";
compress(x, y, size/2); // 2사분면
compress(x, y+size/2, size/2); // 1사분면
compress(x+size/2, y, size/2); // 3사분면
compress(x+size/2, y+size/2, size/2); // 4사분면
cout<<")";
}
return;
}
int main(){
// 입력
cin>>n;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
// 한 줄로 입력받는 데이터를 하나하나 배열에 저장한다
scanf("%1d", &video[i][j]);
}
}
// 압축
compress(1, 1, n);
return 0;
}
|
cs |
+) 큐를 이용
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 | #include <iostream> #include <cstdio> #include <queue> using namespace std; int n; // max 64 int video[65][65]; queue<char> q; void compress(int x, int y, int size){ int first = video[x][y]; int same = true; if( size==1 ){ if( first==0 ) q.push('0'); else if( first==1 ) q.push('1'); return; } for(int i=x; i<x+size; i++){ for(int j=y; j<y+size; j++){ if( first != video[i][j] ){ same = false; } } } if( same ){ if( first ==0 ) q.push('0'); else if( first==1 ) q.push('1'); return; } else{ q.push('('); compress(x, y, size/2); compress(x, y+size/2, size/2); compress(x+size/2, y, size/2); compress(x+size/2, y+size/2, size/2); q.push(')'); } } int main(){ // 입력 cin>>n; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ scanf("%1d", &video[i][j]); } } // 압축 compress(1, 1, n); // 출력 while(!q.empty()){ cout<<q.front(); q.pop(); } cout<<'\n'; return 0; } | cs |
##
4분할해서 탐색하는 순서를 잘못 입력하는 실수! 방문 순서 잘 체크하자
'BOJ' 카테고리의 다른 글
BOJ 1629번 :: 곱셈 (0) | 2019.12.24 |
---|---|
BOJ 1780번 :: 종이의 개수 (0) | 2019.12.24 |
BOJ 9375번 :: 패션왕 신해빈 (0) | 2019.12.23 |
BOJ 2630번 :: 색종이 만들기 (0) | 2019.12.22 |
BOJ 2164번 :: 카드2 (0) | 2019.12.22 |