백준 1992 쿼드 트리

오늘 문제는 쿼드 트리이다!

사실 구현하는거 자체는 그다지 나쁘지 않았다.

4구역을 크기별로 다 확인하면서 만약 다 같은 값으로 이루어져 있다면 출력, 그렇지 않다면 재귀로 한번 더 들어간다.

 

이 문제는 예외들을 생각하지 못해 오래 걸렸다.

우선, 처음부터 다 같은 값으로 들어왔다면 "(", ")" 를 써줄 필요가 없다.

 

그 경우를 위해 처음 입력받을 때 다른 숫자들로 이루어진 입력인가 파악하여아 한다.

 

끝!!

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

string str;
char table[65][65];

void recur(int x, int y, int leng)
{

  if (leng == 0)
    return;
  
  str += "(";
 
  for (int idx = 0; idx < 4; idx++)
  {
    int flag = 0;
    int beginx, beginy;
    if (idx == 0) { beginx = x; beginy = y;}
    if (idx == 1) {beginx = x; beginy = y + leng/2;}
    if (idx == 2) {beginx = x + leng/2; beginy = y;}
    if (idx == 3) {beginx = x + leng/2; beginy = y + leng/2;}

    char comp = table[beginx][beginy];
    for (int i = beginx ; i < beginx + leng/2; i++)
    {
      for (int j = beginy; j < beginy + leng/2; j++)
      {
        if (table[i][j] != comp)
        {
          recur(beginx, beginy, leng/2);
          flag = 1;
          break;
        }
      }
      if (flag == 1)
        break;
    }
    if (flag == 0)
      str+=comp;
  }

  str += ")"; 
}

int main()
{
  int n;


  cin >> n;
  
  for (int i = 0; i < n; i++)
  {
    string str2;
    cin >> str2;
    for (int j = 0; j < n; j++)
    {
      table[i][j] = str2[j];
    }
  }
  char comp = table[0][0];
  int flag = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (table[i][j] != comp)
      {
        flag = 1;
        break;
      }
    }
  }
  if (flag == 0)
  {
    cout<<table[0][0];
    return 0;
  }
  recur(0, 0, n);

  cout << str;
  return 0;
}