알고리즘
[C++] Boj 1992 쿼드트리
(ꐦ •᷄ࡇ•᷅)
2025. 1. 13. 09:41
문제 링크
접근
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;
}
느낀 점
오늘 코드카타는 다행히 예전에 풀어왔던 문제들이랑 비슷해서 쉽게 풀었다. 처음에 이런 재귀 문제를 보면 머릿속이 복잡해졌지만 오늘부터는 이런 스타일의 문제를 완전히 정복했다고 생각이 든다.
처음엔 틀릴지라도 다음에 비슷한 문제가 나왔을 때 맞히면 된다! 그때를 위해 연습하는 것뿐이니 좌절하지 말고 계속 공부하자.