1992번 - 쿼드트리

[ 문제 풀이 ]

1. 입력값이 정수형이 아닌 문자열이다.

따라서, scanf 보다는 cin을 사용했다.
char 변수를 통해 문자열의 한 글자씩 받아서 저장했다.

for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> img[i][j];
        }
}

 

2. 분할하기

N을 길이로 사용해서 계속 절반씩 분할해 나간다.

void QuadTree(int x, int y, int size) {

    int half = size / 2;
    QuadTree(x, y, half);            // 왼쪽 위
    ...
}

3. 재귀사용

설정한 영역의 값이 모두 동일하지 않을 때, 재귀로 4 분할된 영역을 분할탐색하도록 설정했다.

#include <iostream>
using namespace std;

const int MAX = 64; // 최대 크기 64x64
char img[MAX][MAX]; // 입력 이미지 데이터 저장

// 특정 영역이 모두 같은 숫자인지 확인하는 함수
char checkData(int x, int y, int size) {
    char first = img[x][y]; // 첫 번째 값 기준
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (img[i][j] != first) return '2'; // 값이 다르면 '2' 반환
        }
    }
    return first; // 모두 같다면 해당 값 반환
}

// 쿼드 트리 압축 함수
void QuadTree(int x, int y, int size) {
    char check = checkData(x, y, size);
    
    if (check != '2') { // 모두 같은 숫자인 경우
        cout << check;
        return;
    }
    
    // 다른 숫자가 존재하면 4분할 진행
    cout << "(";
    int half = size / 2;
    QuadTree(x, y, half);            // 왼쪽 위
    QuadTree(x, y + half, half);      // 오른쪽 위
    QuadTree(x + half, y, half);      // 왼쪽 아래
    QuadTree(x + half, y + half, half); // 오른쪽 아래
    cout << ")";
}

int main() {
    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> img[i][j];
        }
    }

    QuadTree(0, 0, N);
    cout << "\n"; // 줄 바꿈
    return 0;
}