본문 바로가기
알고리즘 문제풀이/백준

[백준 1992] 쿼드트리

by m2162003 2020. 12. 13.

www.acmicpc.net/problem/1992

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는

www.acmicpc.net

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

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

 

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

(,)는 압축한 횟수 만큼 추가되므로 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;
}

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1495] 기타리스트  (0) 2020.12.13
[백준 1074] Z  (0) 2020.12.13
[백준 5904] Moo 게임  (0) 2020.12.12
[백준 1780] 종이의 개수  (0) 2020.12.12
[백준 16505] 별  (0) 2020.12.12

댓글