[재귀][분할 정복] 1992 쿼드트리 c++ 구현

목차

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

문제

 

문제 구현 방향

구간을 4개로 나누어 재귀만 잘해주면 금방 풀리는 문제이다.

또한 기저사례만 잘 만들어 주면 된다.

 

 

문제 풀이 시 주의점

아래와 같이 그리드를 반으로 나누면 무한 루프에 빠진다.. 주의하자!

시작점과 종점의 중간값으로 해야한다.

void quad(int startx, int starty, int endx, int endy) {
    if (check(startx, starty, endx, endy)) {
        cout << board[starty][startx];
        return;
    }

    int nx = endx / 2;
    int ny = endy / 2;
    cout << '(';
    quad(startx, starty, nx, ny);
    quad(nx+1, starty, endx, ny);
    quad(startx, ny+1, nx, endy);
    quad(nx+1, ny+1, endx, endy);
    cout << ')';

}

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>

using namespace std;


int board[65][65] = { 0 };

int check(int startx, int starty, int endx, int endy) {
    int flag =0;
    for (int i = starty; i <= endy; i++) {
        for (int j = startx; j <= endx; j++) {
            if (i == starty && j == startx)
                flag = board[i][j];
            if (flag != board[i][j])
                return 0;
        }
    }
    return 1;
}

void quad(int startx, int starty, int endx, int endy) {
    if (check(startx, starty, endx, endy)) {
        cout << board[starty][startx];
        return;
    }

    int nx = (startx+endx) / 2;
    int ny = (starty+endy) / 2;
    cout << '(';
    quad(startx, starty, nx, ny);
    quad(nx+1, starty, endx, ny);
    quad(startx, ny+1, nx, endy);
    quad(nx+1, ny+1, endx, endy);
    cout << ')';

}

int main() {
    int num;
    string str;
    cin >> num;
    for (int i = 0; i < num; i++) {
        cin >> str;
        for (int j = 0; j < num; j++) {
            board[i][j] = str[j] - '0';
        }
    }

    quad(0,0, num-1, num-1);

    return 0;
}