boj 1992

boj 1992 쿼드트리 c++

 

이 유형을 마주친 횟수가 점차 증가하고 있다. 처음 머릿 속으로 끙끙 앓으며 풀고난 이후로는 너무나 쉽게 구현하고 있다.

지난번 포스트 와 비슷하게 재귀를 이용해 풀 수 있으며 재귀 함수에서 필요로 하는 정보는 시작 위치 i와 시작 위치 j 그리고 크기 n이다.

여기서 i, j 는 x, y 좌표라고 생각하면 쉬울 듯하다.

 

#include <bits/stdc++.h>
using namespace std;

int N;
string board[65];

void solve(int start_i, int start_j, int n)
{
    bool is_all_same = true;
    char first_element = board[start_i][start_j];
    for (int i = start_i; i < start_i + n; i++)
    {
        for (int j = start_j; j < start_j + n; j++)
        {
            if (board[i][j] != first_element)
            {
                is_all_same = false;
                break;
            }
        }
        if (is_all_same == false)
            break;
    }


    if (is_all_same == true)
        cout << first_element;
    else
    {
        cout << '(';
        for (int i = start_i; i < start_i + n; i += (n / 2))
        {
            for (int j = start_j; j < start_j + n; j += (n / 2))
            {

                solve(i, j, (n / 2));

            }
        }
        cout << ')';
    }
}

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

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string line;
        cin >> line;
        board[i] = line;
    }
    solve(0, 0, N);

}

 

백준 1992 쿼드트리 cpp