[C++] BAEKJOON 1992 퀴드트리

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

1992번: 쿼드트리

분할정복 을 사용하여 문제를 해결하였습니다.

주어진 크기에 대해서 4개로 나누어 부분 문제로 나누어 접근하였습니다. 현재 크기에 대해서 모든 값이 같은지 확인하는 check 함수와 전부 같다면 그 값을 출력하고, 다르다면 () 를 출력하고 부분문제로 나누는 solve 함수를 사용하였습니다.

#include <iostream>

using namespace std;

int board[64][64];

int check(int y,int x,int N){
    int temp = board[y][x];
    for (int i=y;i<y+N;i++){
        for (int j=x;j<x+N;j++){
            if (temp != board[i][j]){
                return 0;
            }
        }
    }
    return 1;
}

void solve(int y,int x,int N){
    if (N==0) return ;
    
    else if (check(y,x,N)){
        cout << board[y][x];
    }
    else {
        cout << "(";
        int M = N/2;
        for (int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                solve(y+i*M,x+j*M,M);
            }
        }
        cout << ")";
    }
}

int main(int argc, const char * argv[]) {
    
    int N;
    cin >> N;

    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            scanf("%1d", &board[i][j]);
        }
    }
    solve(0,0,N);
    return 0;
}