#문제

https://www.acmicpc.net/problem/1992

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

www.acmicpc.net

 

#작성 코드

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이라면 무조건 출력한다.(더이상 분할할수없으므로) 
    ifsize==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/2size/2);            // 1사분면 
        compress(x+size/2, y, size/2);            // 3사분면 
        compress(x+size/2, y+size/2size/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(11, 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;
    ifsize==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/2size/2);
        compress(x+size/2, y, size/2);
        compress(x+size/2, y+size/2size/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(11, 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

+ Recent posts