1992번 - 쿼드트리 (C++)

[문제]

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

1992번: 쿼드트리

 

[풀이]

이전 문제와 똑같이 재귀함수로 푸는 문제이다. vector를 이용하여 쿼드트리를 저장하였음. test함수에서 모두 0, 1로 되어있는지 판단하고, 아니면 false, 맞으면 true 값을 반환하였다.

true인 경우 1 혹은 0을 벡터에 넣어 쿼드 트리 완성, 괄호는 재귀함수에 넣을때 같이 벡터에 넣어주었고 숫자 사이에 괄호를 없애서 문제를 풀었다.

 

---

[코드]

#include <bits/stdc++.h>

using namespace std;

char arr[100][100];
vector<char> v;

bool test(int x, int y, int N)
{
    for(int i=x; i<x+N; i++)
    {
        for(int j=y; j<y+N; j++)
        {
            if(arr[x][y] != arr[i][j])
                return false;
        }
    }
    return true;
}

void check(int x, int y, int N)
{
    if(test(x,y,N) == true)
    {
        if(arr[x][y] == '1') {
            v.push_back('1');
        }
        else if(arr[x][y] == '0'){
            v.push_back('0');
        }
        return;

    }
    for(int i=x; i<x+N; i+=N/2)
    {
        for(int j=y; j<y+N; j+=N/2)
        {
            v.push_back('(');
            check(i,j,N/2);
           
        }
    }
    v.push_back(')');
}   

int main() {
    int N;
    cin >> N;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    bool first = false;
    check(0,0,N);
    for(int i=0; i<v.size(); i++)
    {
        if((v[i] == '0' || v[i] == '1') && first == false){
            first = true;
            continue;
        }
        if(v[i] == '0' || v[i] == '1')
        {
            if(i != 0 && first == true)
            {
                v.erase(v.begin()+i-1);
            }
        }
    }
    for(int i=0; i<v.size(); i++)
    {
        cout << v[i];
    }
    
}