boj 1992

Algorithm / / 2021. 2. 26. 11:59

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

 

'Algorithm' 카테고리의 다른 글

프로그래머스 기능개발 c++  (0) 2021.05.23
프로그래머스 소수 만들기 c++  (0) 2021.05.23
boj 1780  (0) 2021.02.25
boj 1003 피보나치 함수 c++  (0) 2021.02.19
boj 18111 마인크래프트 c++  (0) 2021.02.18
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기
// custom