[cpp 알고리즘] 백준 1992 쿼드트리

[백준] 1992 쿼드트리 풀이

분할정복, 재귀

문제 출처: https://www.acmicpc.net/problem/1992

 

문제 요약

예시 문제

- 모두 0으로만 되어 있으면 압축 결과는 "0"

- 모두 1로만 되어 있으면 압축 결과는 "1"

- 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지 않고, "왼쪽 위/ 오른쪽 위/ 왼쪽 아래/ 오른쪽 아래" 4개로 나누어 압축하고, 이 4개의 영역을 압축한 결과를 괄호 안에 묶어서 표현

 

예시 문제의 경우: (0(0011)(0(0111)01)1) 로 표현된다.

풀이 정리

1. 모두 0인지 확인, 모두 1인지 확인, 그렇지 않다면 분할정복

2. 분할정복 할 때 n=1인 경우는 먼저 종료시키고 아니면 1의 과정을 반복한다. 

c++ 코드

#include <iostream>
#include <string>
using namespace std;

int N;
int arr[65][65];

void divide(int y, int x, int n) {
    //cout << y << " " << x << " " << n << "\n";
    if(n==1) {
        cout << arr[y][x];
        return;
    }
    
    bool zero = true;
    bool one = true;
    for(int i=y; i<y+n; i++){
        for(int j=x; j<x+n; j++){
            if(arr[i][j] == 0) one = false;
            else if(arr[i][j] == 1) zero = false;
        }
    }
    
    if(zero){
        cout << 0;
    }
    else if(one){
        cout << 1;
    }
    else{
        //4분할
        cout << "(";
        divide(y, x, n/2);
        divide(y, x+(n/2), n/2);
        divide(y+(n/2), x, n/2);
        divide(y+(n/2), x+(n/2), n/2);
        cout << ")";
    }
}

int main() {
    cin >> N;
    for (int y=0; y<N; y++) {
        string s; cin >> s;
        for (int x=0; x<N; x++) {
            arr[y][x] = s[x]-'0';
        }
    }
    
    divide(0,0,N);
    return 0;
}

 

기타

백준 1992 쿼드트리 풀이

 

- 공백없이 input을 받은 다음에 배열에 넣고자 할 때) string으로 받아서 하나씩 나누기

- 배열[y좌표][x좌표] 순서