백준 1992 쿼드트리

문제 URL : https://www.acmicpc.net/problem/1992

 

문제 접근법:

1.재귀 함수를 이용해서 문자하나를 기준으로잡고 처음 0,0부터 n-1,n-1 까지 확인한다음 모든 것이 같은지 혹은 다른것이있는지 확인하고 모두 같은지 혹은 하나라도 다른지 같으면 기준이된 문자열을 반환하고

다르다면 왼쪽상단 오른쪽상단 왼쪽하단 오른쪽 하단으로

나누어서 계속 확인하는 방식으로 만약 나누게 된다면 중괄호를 넣어주면 되기때문에

아이디어가 있다면 코드는 굉장히 쉽게 풀립니다.

 

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 53 54 55 56 57 58 59 60 61

#include <iostream> #include <queue> #include <vector> #include <string> using namespace std; char quad[64][64]; bool same(int y, int x, int size){     char c = quad[y][x];     bool isdivide = false;     for (int i = y; i <y+size; i++)     {         for (int j = x; j <x+ size; j++)         {             if (c != quad[i][j]){                 isdivide = true;                 break;             }         }         if (isdivide)             break;     }     return isdivide; } string makequad(int y,int x,int size){     char c = quad[y][x];     bool isdivide = same(y,x,size);     string res;     if (isdivide)//나눠야한다면     {         int half = size / 2;         //중괄호를 먼저넣어줌         res += "(";         //4개의 영역으로 나눔         res+=makequad(y, x, half);//왼쪽상단         res+=makequad(y, x + half, half);//오른쪽상단         res += makequad(y + half, x, half);//왼쪽하단         res += makequad(y + half, x + half, half);//오른쪽하단         res += ")";     }     else//나누지않는다면 그냥 y,x좌표만 꺼내가면됨     {         res += c;     }     return res; } int main(void) {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     int n;     cin >> n;     for (int i = 0; i < n; i++)     {         for (int j = 0; j < n; j++)         {             cin >> quad[i][j];         }     }     cout << makequad(0, 0, n) << "\n"; } Colored by Color Scripter

cs

 

모두 열공해봐요 ㅎㅎ