[백준] 1992번 쿼드트리

문제: 1992번: 쿼드트리

basic-algo-lecture/workbook/0x0B.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0B.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

void Count(int n, int x, int y, vector<vector<char>>& board) {
    int tmpZero = 0;

    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (board[i][j] == '0')
                tmpZero++;
        }
    }

    // 한 가지 숫자로만 이루어진 경우는 그냥 출력
    if (tmpZero == 0)
        cout << 1;
    else if (tmpZero == n * n)
        cout << 0;
    else {
        // 한 가지 숫자로 이루어지지 않은 경우는 4분할 해야함
        cout << "(";

        int half = n / 2;
        Count(half, x, y, board);
        Count(half, x, y + half, board);
        Count(half, x + half, y, board);
        Count(half, x + half, y + half, board);

        cout << ")";
    }
    return;
}


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

    int n;
    cin >> n;
    vector<vector<char>> board(n);
    for (int i = 0; i < n; i++) {
        board[i] = vector<char>(n);
        string input;
        cin >> input;

        for (int j=0; j<n; j++) {
            board[i][j] = input[j];
        }
    }
    Count(n, 0, 0, board);


    return 0;
}

 

음.. 이 문제도 2630번 색종이 만들기 문제랑 딱히 다를 바가 없었다.

 

다른 점이라고 하면 2630번은 각 색종이의 개수를 출력하는 거고 이 문제는 각 단계의 색종이의 번호를 출력하는 것?

 

코드 상에서는 진짜 달라진 부분이 거의 없다. 일단 Count 메서드에 진입하면 색종이를 확인해서 모두 같은 번호로 되어 있는지 확인하고 맞다면 색종이의 번호를 출력, 아니라면 4분할 하면 된다.

 

4분할 하기 전에 ( 를 출력해주고 분할을 끝마치면 ) 을 출력해주면 쉽게 문제를 해결할 수 있다.

 

 

 

참고자료:

[바킹독의 실전 알고리즘] 0x0B강 - 재귀 - YouTube