쿼드트리(x)

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

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<int>> v;
string s;

string DFS(int y, int x, int k)
{
    if (k == 1)
        return string(1, v[y][x]);
    string result{};
    char temp = v[y][x];

    for (int i = y; i < k+y; i++)
    {
        for (int j = x; j < k+x; j++)
        {
            if(temp != v[i][j])
            {
                result += '(';
                result += DFS(y, x, k / 2);
                result += DFS(y, x+k/2, k/2);
                result += DFS(y+k/2, x, k/2);
                result += DFS(y+k/2, x+k/2, k/2);
                result += ')';
                return result;
            }
        }
    }

    return string(1, v[y][x]);
}

int main()
{
    cin >> n;
    v.resize(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        for (int j = 0; j < n; j++)
        {
            v[i][j] = s[j];
        }
    }

    cout << DFS(0, 0, n) << endl;

}

• 쿼드 트리 문제는 0,0에서부터 n,n까지 순회하면서 모두가 0 또는 1이라면 0 또는 1을 출력하고 그렇지 않다면 현재 배열을 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래로 4등분하여 다시 탐색한다
• 이처럼 같지않은 숫자가 나오면 계속해서 4등분하여 같은 숫자들끼리 모였을 때 그 숫자로 압축하는 문제이다
• 밑의 그림을 보면 쉽게 이해할 수 있을것이다
• 이처럼 4등분을 하게되면 Z짜 모양으로 탐색하는데 이때 기본 로직은 같고 매개변수들만 달라질것이란게 보이므로 재귀함수를 이용해 풀면 되는 문제이다
• 또한 변하는 매개변수는 시작지점의 y,x축, 배열의 길이 이렇게 3개가 변할것이다
• 문제에서 값을 입력받을 때 평소와는 달리 띄어쓰기가 없이 string으로 한줄한줄 입력받게끔 되어있을 것이다
• 그래서 2중 for문을 이용해 입력받은 string의 원소 하나하나를 저장해줘야 한다
• 재귀함수를 이용해 결과 값을 string result; 변수에 저장해줄 것이고, char temp 변수에는 현재 위치에 해당하는 배열값을 저장해준다
• 이중 for문을 통해 temp와 배열에 index를 대입한 값이 같은지 틀린지를 판단해 줄것인데 이때 i = y부터 j = x부터 시작하여 시작지점이 변할 수 있게 해주고, y+k, x+k 까지 반복을 하게 하여 k가 줄어도 y,x부터 시작해 k길이까지 반복해서 갈 수 있게 해준다
• temp와 현재 index의 배열 값이 같지 않다면 4등분으로 나눠주기 위해 result에 (를 저장한 뒤 왼위, 오위, 왼아래, 오아래 순으로 재귀 함수를 호출할 수 있게 해줄것인데 이를 계산해보면 (y,x,k/2) , (y,x+k/2,k/2), (y+k/2,x,k/2), (y+k/2,x+k/2,k/2) 순으로 재귀함수를 호출해주면 된다
• 이 재귀 함수를 모두 돌고나면 return을 꼭 해줘야 하는데 그 이유는 4등분을 해서 결과를 다 도출했지만 반복분에 i,j값이 아직 조건에 참이므로 반복문이 더 돌아가는 것을 방지하고 끝내기 위해서이다
• 또한 함수 탈출 조건으로 k == 1일때 현재 배열의 index값을 1번만 return하게 해주어 굳이 필요없는 연산을 안하게 해주고, 마찬가지로 함수 맨 마지막에도 배열의 index값을 1번만 return하게해주어 반복문에서 if문에 걸리지 않고 끝이 났을 때 k * k 배열에서 모두 같은 숫자로 압축을 한것이므로 return해주는 것이다