[백준][1992] 쿼드 트리

이 포스트는 백준 사이트의 쿼드 트리 문제 풀이입니다.

문제

해결 과정

이 문제는 문제를 작은 문제로 나눠 해결하는 DP를 활용해 풀 수 있습니다.

사각형이 4개의 부분으로 나뉘었을 때, 방문하는 순서는 아래와 같습니다.

1	2
3	4

재귀 함수를 이용한 방문을 처리하면 1번부터 4번까지 한 번씩 탐색을 하면 됩니다.
괄호가 입력되는 순간은 현재 탐색되는 부분에서 한 깊이 더 내려갈 때, 괄호를 출력하면 됩니다.

코드에서 주의할 점은 N의 크기가 1이거나
이미 사각형이 압축 가능한 형태(모든 위치의 값이 동일)라면
재귀 함수를 호출할 필요가 없습니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> board;

bool check_board(int row, int col, int size);
void DP(int row, int col, int size);


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    board.assign(N + 1, vector<int>(N + 1, 0));
    for(int row = 1; row <= N; ++row) {
        string str;
        cin >> str;
        for(int col = 1; col <= N; ++col) {
            board[row][col] = int(str[col - 1] - '0');
        }
    }

    if(N == 1 || check_board(1, 1, N)) {
        printf("%d", board[1][1]);
    } else {
        printf("(");
        DP(1, 1, N / 2);
        printf(")");
    }

    return 0;
}


bool check_board(int row, int col, int size) {
    int curr_sign = board[row][col];
    for(int r = row; r < row + size; ++r) {
        for(int c = col; c < col + size; ++c) {
            if(curr_sign != board[r][c]) return false;
        }
    }
    return true;
}

void DP(int row, int col, int size) {
    if(check_board(row, col, size)) {
        printf("%d", board[row][col]);
    }
    else {
        printf("(");
        DP(row, col, size / 2);
        printf(")");
    }

    if(check_board(row, col + size, size)) {
        printf("%d", board[row][col + size]);
    }
    else {
        printf("(");
        DP(row, col + size, size / 2);
        printf(")");
    }

    if(check_board(row + size, col, size)) {
        printf("%d", board[row + size][col]);
    }
    else {
        printf("(");
        DP(row + size, col, size / 2);
        printf(")");
    }

    if(check_board(row + size, col + size, size)) {
        printf("%d", board[row + size][col + size]);
    }
    else {
        printf("(");
        DP(row + size, col + size, size / 2);
        printf(")");
    }
}

실행 결과