[백준]1992번: 쿼드트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

---

전형적인 분할 정복 문제!

 

이번에는 오랜만에 C++로 풀어봤다.

 

✅ 문제 풀 때 주의할 점

아래 테스트케이스들 정도만 주의하면 되는 것 같다.

저걸 고려 안 해서 고생 좀 했다 🥲

 

# input1

2

11

11

# output1

1

 

# input2

2

10

01

# output2

(1001)

 

✅ 아이디어

 - 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 총 4개 영역을 나누어서 하나씩 검사한다.

 - 영역의 첫 번째 숫자를 저장한 뒤, 영역을 탐색하면서 하나라도 다르면 탐색을 중지하고 재귀한다.

 - 영역의 숫자가 모두 동일하면 숫자를 결과 string에 저장한다.

 

✅ 제출 코드

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

using namespace std;

char table[64][64];

string quad(int row, int col, int qSize){ // 시작행, 시작열, 체크할 영역 크기
  
  string result; result += '(';

  int area = qSize/2;
  
  int startR[4] = {row, row, row+area, row+area};
  int startC[4] = {col, col+area, col, col+area};

  for(int k=0; k<4; k++){
      //current row, current col
    int cr = startR[k]; int cc = startC[k];
    char first = table[cr][cc];
    bool flag = true;
    for(int i=cr; i<cr+area; i++){
      for(int j=cc; j<cc+area; j++){
        if (table[i][j]!=first){
          result += quad(cr, cc, area);
          flag = false;
          break;
        }
      }
    if (!flag) break;
    }
  if (flag) result += first;
  }
return result+')';
}

int main() {

  // 인풋 입력받고 저장하기
  int n; cin >> n;
  for (int i=0; i<n; i++){
    string temp; cin >> temp;
    for (int j=0;j<n;j++){
      table[i][j] = temp[j];
    }
  }

  // 압축이 한 번에 되는지 체크
  bool flag = true;
  char first = table[0][0];
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(first != table[i][j]){
        flag = false; break;
      }
    }
    if (!flag) break;
  }

  // 압축이 한 번에 되면 결과 출력
  if(flag) cout<<first;
  //그렇지 않으면 quad함수 실행
  else cout << quad(0,0,n);
  
  return 0;
}