[백준 1992] 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

재귀문제이다. 이전 문제와 약간의 차이가 있다면 (를 추가로 붙이는 거 정도

이전과 동일하게 압축할 정사각형의 길이, 정사각형 시작점을 인자로 받는다.

 

헷갈렸던 점은 (를 어디에 붙여야 하나...했던 점이다. 

(,)는 압축한 횟수 만큼 추가되므로 4개로 나눠서 압축을 시작하는 전후에 붙여주면 된다.

#include <stdio.h>

using namespace std;

char arr[65][65];
int n;

bool isSame(int len, int row, int col)
{
  char cmp = arr[row][col];
  for (int i = 0; i < len; i++)
  {
    for (int j = 0; j < len; j++)
    {
      if (cmp != arr[row + i][col + j])
      {
        return false;
      }
    }
  }
  return true;
}

void quadTree(int len, int row, int col)
{
  if (len == 1)
  {
    printf("%c", arr[row][col]);
    return;
  }

  if (isSame(len, row, col))
  {
    printf("%c", arr[row][col]);
    return;
  }

  len = len / 2;
  printf("(");
  for (int i = 0; i < 2; i++)
  {
    for (int j = 0; j < 2; j++)
    {
      quadTree(len, row + len * i, col + len * j);
    }
  }
  printf(")");
}

int main(void)
{
  scanf("%d", &n);

  for (int i = 0; i < n; i++)
  {
    scanf("%s", arr[i]);
  }

  quadTree(n, 0, 0);
  return 0;
}