[1992번] 쿼드트리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 분할 정복

이 문제는 분할 정복으로 해결 할 수 있다.

위와 같이 쿼드 트리 문제는 2^k단위로 입력값이 주어지고 결국 4분할 할 수 있도록 문제 입력이 주어진다.

따라서 저 과정을 하기위해 계속 분할시키고, n == 1 즉, 1개만 보고있을 때는 return을 하게 해준다.

그다음부터는 이제 자신이 리턴받은 모든 값이 같다면 압축, 그렇지 않다면 각각의 수를 return하면 된다.

이 과정을 코드로 제작하면 문제가 자연스럽게 해결된다.

소스 코드 : 

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

#include <iostream> #include <cstdio> #include <string>   using namespace std;   string arr[100];   string solve(int n, int y, int x, int jump) {     if (n == 1)     {         string res = "";         res += arr[y][x];         return res;     }       string first = "";     first += arr[y][x];     string lu = solve(n / 2, y, x, jump / 2);     string ru = solve(n / 2, y, x + jump, jump / 2);     string ld = solve(n / 2, y + jump, x, jump / 2);     string rd = solve(n / 2, y + jump, x + jump, jump / 2);       // 모두 같은 숫자일경우 압축     if (lu == first && ru == first && ld == first && rd == first)         return first;       // 그 외에는 그냥 보내기     return '(' + lu + ru + ld + rd + ')'; }   int main() {     int n;     scanf("%d", &n);       getchar();     for (int i = 0; i < n; i++)         getline(cin, arr[i]);          cout << solve(n, 0, 0, n / 2);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus