[C++] 백준 1992 - 쿼드트리

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

1992번: 쿼드트리

<풀이>

1. 주어진 영상을 입력받는다.

2. 영상이 모두 0 또는 1로 되어있을 경우 값을 저장한다.

3. 모두 0 또는 1이 아닐경우 영상을 4개로 나눈다.

4. 2,3번을 종료될 때까지 반복진행한다.(재귀함수)

#include <iostream>
#include <vector>
using namespace std;
 
int N;
int map[64][64];
vector<char> res;
 
void go(int n, int x, int y) {
 
    //부분이 모두 0 또는 1 인지 검사
    bool allZero = true;
    bool allOne = true;
 
    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (map[i][j] == 1) {
                allZero = false;
            }
            else {
                allOne = false;
            }
        }
    }
 
    //종료조건
    if (allZero || allOne) {
        if (allZero) {
            res.push_back('0');
        }
        else {
            res.push_back('1');
        }
        return;
    }
 
    //4부분 탐색
    res.push_back('(');
    go(n / 2, x, y);
    go(n / 2, x, y + (n / 2));
    go(n / 2, x + (n / 2), y);
    go(n / 2, x + (n / 2), y + (n / 2));
    res.push_back(')');
 
    return;
}
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf_s("%1d", &map[i][j]);
        }
    }
 
    //go(변길이, 시작지점 i, 시작지점 j)
    go(N, 0, 0);
 
    //출력
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
}

 

재귀함수에 대해 알아볼 수 있는 문제였습니다.