[C++/백준] 1992번: 쿼드트리

문제 링크

1992번: 쿼드트리

 

풀이

분할 정복 문제

1. 먼저 모두 같은지 확인하는 check함수로 해당 영역이 모두 같은 숫자라면 true, 아니라면 false를 return한다.
   1. 영역이 모두 같으면 answer에 해당 숫자를 추가한다.
2. 아니라면 영역을 나눠주는데, (괄호를 먼저 추가하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀호출한다. 이 때 size는 반으로 줄여준다.
3. 모든 호출이 끝나면 answer에 )괄호를 추가해준다.

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string answer = "";

bool check(vector<vector<char>> &v, int size, int y, int x)
{
    char c = v[y][x];
    for (int i = y; i < y + size; i++)
    {
        for (int j = x; j < x + size; j++)
        {
            if (c != v[i][j]) return false;
        }
    }
    return true;
}

void func(vector<vector<char>> &v, int size, int y, int x)
{    
    if (check(v, size, y, x))
    {
        answer += v[y][x];
    }
    else
    {
        answer += '(';
        func(v, size / 2, y, x); // 왼쪽 위
        func(v, size / 2, y, x + size / 2); // 오른쪽 위
        func(v, size / 2, y + size / 2, x); // 왼쪽 아래
        func(v, size / 2, y + size / 2, x + size / 2); // 오른쪽 아래
        answer += ')';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

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

    func(v, n, 0, 0);

    cout << answer << endl;

    return 0;
}