쿼드트리(Silver 1)
문제
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
접근법
이번 문제는 분할정복으로 풀 수 있습니다. 우선 현재 입력받은 범위 내에서 모든 수가 같은지 확인하는 Check 함수를 만듭니다. 이 Check함수를 활용해서 모든 수가 같은지 확인 후 같다면 해당 수를 출력하고, 같지 않다 배열의 범위를 4곳으로 나누어 재귀적으로 호출합니다. 코드는 다음과 같습니다.
전체 풀이
#include <stdio.h>
#include <string>
#include <vector>
#define endl '\n'
using namespace std;
const int MAX = 64;
// 해당 범위 내에서 모든 수가 같다면 true 하나라도 다르면 false
bool Check(vector<string>&img, int x, int y, int size)
{
for (int j = y; j < y + size; ++j)
for(int i = x; i < x + size; ++i)
{
if (img[y][x] != img[j][i]) return false;
}
return true;
}
// 분할 정복 함수
void Division(vector<string>& img, int x, int y, int size)
{
// 단일 문자일 경우
if (Check(img, x, y, size))
{
printf("%c", img[y][x]);
return;
}
// 단일 문자가 아닐 경우
printf("(");
int half = size / 2;
Division(img, x, y, half);
Division(img, x + half, y, half);
Division(img, x, y + half, half);
Division(img, x + half, y + half, half);
printf(")");
return;
}
int main() {
int N; // 1 ≤ N ≤ 64의 범위
scanf("%d ", &N);
vector<string> img(N);
for (string& row : img)
{
char temp[64];
scanf("%s\n",temp);
row = temp;
}
Division(img, 0, 0, N);
return 0;
}성능 평가
이 풀이에서 재귀함수를 살펴봅시다. 각 탐색의 깊이마다 Check 함수에서 모든 원소를 한번씩 탐색합니다. 그리고 탐색의 깊이는 전체 원소를 4 등분씩 나누어 들어가기 때문에 log에 비례합니다. 전체 노드의 개수는 \(N^2\) 이기 때문에 전체 시간 복잡도는 \(O(N^2\mbox {log} N)\)입니다. 공간 복잡도는 전체 원소의 개수만큼의 배열이 필요하기 때문에 \(O(N^2)\)입니다.
