[0612] 알고리즘

1992. 쿼드트리

  과정 자체는 어제 풀었던 문제와 거의 흡사했다. 주어진 수의 배열을 4분할하고 각각의 분할에 대해 모든 항목이 똑같은지를 검사한 후, 똑같지 않으면 다시 재귀를 통해 분할을 하는 방식. 대신 압축한 결과값을 괄호로 묶인 문자열로 표현해야 하기 때문에 string 헤더 파일을 사용해서 문자열을 만들었다.

 

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

int square[65][65];
std::string zip;

void Divide(int col, int row, int side);

int main()
{
  std::cin.tie(NULL);

  int n;

  std::cin >> n;  

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      scanf("%1d", &square[i][j]);
    }
  }

  Divide(0, 0, n);

  std::cout << zip << '\n';

  return 0;
}

void Divide(int col, int row, int side)
{
  bool isDone = false;

  for (int i = col; i <= col + side - 1; i++)
  {
    for (int j = row; j <= row + side - 1; j++)
    {
      if (square[col][row] != square[i][j])
      {
        zip.push_back('(');
        Divide(col, row, side / 2);        
        Divide(col, row + side / 2, side / 2);
        Divide(col + side / 2, row, side / 2);
        Divide(col + side / 2, row + side / 2, side / 2);
        zip.push_back(')');
        isDone = true;

        break;
      }
    }

    if (isDone) break;
  }

  if (!isDone && square[col][row] == 1)   
    zip.push_back('1');

  else if (!isDone && square[col][row] == 0)
    zip.push_back('0');
}

---

 

  사실상 어제 푼 문제를 거의 날먹한 코드.

  string 헤더파일을 사용하면 마치 배열처럼 문자열을 사용할 수 있다는 게 엄청나게 편한 것 같다. 여러모로 C 처음 배웠을 때는 상상하지도 못했던 편리함을 겪어보는 중.