[C++] Boj 1992 쿼드트리

문제 링크

1992 쿼드트리

접근

1. 함수식

void Solve(int x, int y, int n) // n은 데이터의 범위

2. base condition

n == 1일때, 해당 데이터는 무조건 출력

3. 재귀식

void Solve(x, y, n)
{
	// "("을 출력
    if(//모두 같은 데이터인지 확인)
    {
    	// 같은 데이터라면
        // 데이터 출력
    }
    else // 같은 데이터가 아니라면
    {
    	// "("을 출력
    	Solve(x, y, n / 2)
        ...
        // 4등분하고, 모든 부분마다
        // 재귀 함수 시작
        
        // ")"을 출력
    }
}

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;

int data[65][65];
int N;

// 같은 데이터인지 확인
bool CheckData(int x, int y, int n)
{
    int type = ::data[x][y];
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++)
        {
            if (::data[i][j] != type)
                return false;
        }
    }

    return true;
}

void Solve(int x, int y, int n)
{
    if (CheckData(x, y, n))
    {
        printf("%d", ::data[x][y]);
    }
    else
    {
        printf("(");
        int half = n / 2;
        Solve(x, y, half);
        Solve(x, y + half, half);
        Solve(x + half, y, half);
        Solve(x + half, y + half, half);
        printf(")");
    }
}


int main()
{
    // 데이터 입력 받음
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%1d", &::data[i][j]);
        }
    }
    
    Solve(0, 0, N);

    return 0;
}

느낀 점

오늘 코드카타는 다행히 예전에 풀어왔던 문제들이랑 비슷해서 쉽게 풀었다. 처음에 이런 재귀 문제를 보면 머릿속이 복잡해졌지만 오늘부터는 이런 스타일의 문제를 완전히 정복했다고 생각이 든다. 

처음엔 틀릴지라도 다음에 비슷한 문제가 나왔을 때 맞히면 된다! 그때를 위해 연습하는 것뿐이니 좌절하지 말고 계속 공부하자.