[c++] 백준 1992 - 쿼드트리

0. [c++] 백준  -

https://www.acmicpc.net/problem/1992

1. 풀이

1) 분할 정복을 이용해서 풀이하면 좋을 것이라고 판단되었다. 그래서 일단 무조건 N>1인 경우에는 사분할을 하고, 그 과정을 통해 N이 1이 될 때 까지 한다.

2) N=1이 되었을 때, 자신의 위치에 있는 숫자를 반환한다.

3) 이제 다시 N=2로 올라와서 N=1에 있는 것들이 동일하면, 다시 위로 올라가고, 아닌경우 (a1,a2,a3,a4)의 형태로 출력을 하는 함수를 만들려고 구상을 하였지만....

하다가 조금 막혀서 그냥 brute force로 구현을 하였다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include<iostream> #include<string>   using namespace std;   const int MAX_INT = 64;   int arr[MAX_INT][MAX_INT];   int quadTree(int N, int y, int x) {     //기저 사례: N이 1인 경우 자기 자신을 반환     if (N == 1) {           cout <<arr[y][x];         return 0;     }          int find = arr[y][x];     int half = N / 2;     for (int i = y; i < y + N; i++)          for (int j = x; j < x + N; j++) {             //기저 사례: 만일 구간 내에 자신과 다른 인자가 있는 경우, 4개로 나누어 압축한다.             if (find != arr[i][j]) {                 cout << "(";                 quadTree(half, y, x);                 quadTree(half, y, x + half);                 quadTree(half, y + half, x);                 quadTree(half, y + half, x + half);                 cout << ")";                 return 0;             }         }     //모든 인자가 같은 경우이므로 자기 자신을 출력     cout << find;     return 0; }   int main() {     int N;     string num;     cin >> N;     for (int i = 0; i < N; i++) {         cin >> num;         for (int j = 0; j < N; j++)             arr[i][j] = num[j] - '0';     }       quadTree(N, 0, 0);         return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!