1992 : 쿼드트리 - 분할 정복(Divide and Conquer) , 재귀 함수

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

1992번: 쿼드트리

문제요약

4분면을 나누어 탐색 후 압축하여 출력

 

난이도

Silver 1

---

풀이 포인트

• 입력값 받기
  • string 한줄로 받아 인덱스로 접근
  • string 111000을 int형으로 변환하여 받기 1 - '0' 이런 식
• 재귀 함수 짜기
  • 재귀를 짤때는 어떤 로직이 반복되는지 정확히 체크후 반복 돌리기 로봇 청소기
  • 똑같은 로직인데 매개변수만 바뀌는 것
• 분할 정복 ( Divide and Conquer)
  • 문제를 하위 문제로 쪼개어 푸는 것
  • 재귀 또는 stack으로 구현
• string(출력할 문자열의 길이, 문자열)

// 문자 'A'로 초기화된 길이가 5인 문자열 생성
    string str1(5, 'A');
    cout << str1 << endl; // 출력: AAAAA

---

REVIEW

 

쪼개어 생각해볼까 싶어 2*2의 4칸짜리 2차원 벡터를 방향벡터 이용해 z자 탐색후 출력하는 것부터 시작.

 

근데 큰 덩어리를 작은 덩어리로 나누어가는 재귀가 생각하기 편한데,

작은 덩어리로 부터 큰덩어리 탐색으로 거슬러 생각하려니 또 오류.

 

재귀를 짜는 것이 아직은 어려운데,

정확히 어떤 동작이 반복되고 있는지, 그 과정에서 어떤 매개변수가 변하고 있는지를 파악하는 것이 중요.

이 문제의 경우

• 배열의 사이즈와 탐색을 시작하는 시작 좌표가 변하고 (매개변수)
• 0,1로만 이루어져있는지 탐색 , 아니라면 4분할 후 z방향으로 탐색 (반복 동작)

이걸 파악하고 시작하는 것이 좋다.

 

일단은 풀어보고자 4분할을 하는 것과, 0과 1인지 전수 검사를 하는 것으로 구현해 보았으나 틀렸다.

또한 모범 답안에서 내가 구현한 노가다들을 한줄로 축약해 구해내는 로직들이 있으니 공부해두기.

---

CODE

#include <bits/stdc++.h>
using namespace std;

int n; 
string s;
char a[101][101];

string quardTree(int y, int x, int size){

    cout << "현재 (y,x)는 (" <<  y << "," << x <<")"<<'\n';
    cout << "현재 size는 " << size<<'\n';

    if(size == 1) return string(1,a[y][x]);

    char b = a[y][x];
    string ret ="";

    // 일반적 좌표평면에서의 x,y와 2차원 배열에서의 인덱스 i,j가 반대로 매핑되기 때문에
    // y,x 바꿔서 하시는 듯
    // 어차피 탐색 순서(좌상-우상-좌하-우하)가 행별로 탐색우선, 그다음 열으로 가는 2차원 배열 인덱스와 매칭됨
    for(int i = y; i < y + size; i++){
        for(int j = x; j < x + size; j++){
            cout << "탐색 좌표는 (" << i << "," << j << ")" << '\n';

            if(b!=a[i][j])
            {
                cout << "시작 좌표와 탐색 좌표가 달라서 재귀를 시작할 것임"<<'\n';

                ret += '(';
                cout << "괄호가 열렸다\n";
                //좌상-우상-좌하-우하
                ret += quardTree(y,x,size/2);
                ret += quardTree(y,x+ size/2, size/2);
                ret += quardTree(y + size/2, x, size/2);
                ret += quardTree(y + size /2 , x + size/2, size/2);
                ret +=')';
                cout << "괄호가 닫혔다\n";
                return ret;
            }
        }
    }
    // 마지막에 괄호가 어떻게 닫히지?
    // 4가 아니라 8부터 시작하기 때문! 
    
    cout << "시작 좌표와 탐색 좌표가 모두 같아서 0 또는 1을 출력하겠다" << '\n';
    return string(1,a[y][x]);
}

int main(){
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < n; j++){
            a[i][j] = s[j];
        }
    }
    cout << quardTree(0,0,n) << '\n';
    return 0;
}