[BOJ] 2992 - 쿼드트리

문제에 나와있는 그대로 자식이 4개인 트리를 생각하면 된다.

트리는 곧 그래프이고 

그래프를 dfs방식으로 순환하면 된다.

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// dfs

int arr[65][65] = {0};
int N = 0;
int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1};
int node_counter = 0;
bool isMixed(int nx, int ny, int width)
{
    bool isArrayMixed = false;
    if (width == 1)
    {
        return isArrayMixed;
    }

    for (int i = nx; i < nx + width; i++)
    {
        for (int j = ny; j < ny + width; j++)
        {
            if (arr[i][j] != arr[nx][ny])
            {
                isArrayMixed = true;
                return isArrayMixed;
            }
        }
    }

    return isArrayMixed;
}

void dfs(int cx, int cy, int width)
{
    // 기저 사례, 종료 조건
    if (!isMixed(cx, cy, width))
    { // 0과 1로만 이루어져있으면
        cout << arr[cx][cy];
        return;
    }

    int new_width = width / 2;
    int nx, ny;

    cout << "(";
    for (int i = 0; i < 4; i++)
    {
        nx = cx + (dx[i] * new_width);
        ny = cy + (dy[i] * new_width);

        dfs(nx, ny, new_width);
    }
    cout << ")";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    string str;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> str;
        for (int j = 0; j < str.size(); j++)
        {
            arr[i][j] = str[j] - '0';
        }
    }

    dfs(0, 0, N);
}

 

맞았으나 메모리 낭비한 코드 (쓸데없이 트리를 인접리스트에 저장한 뒤, 인접리스트를 for문으로 돌며 정답을 출력)

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
//인접리스트 + dfs

typedef struct node
{
    int node_num; // -1은 리프노드
    int data;
} node;

vector<node> tree[10000];
int arr[65][65] = {0};
int N = 0;
int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1};
int node_counter = 0;
bool isMixed(int nx, int ny, int width)
{
    bool isArrayMixed = false;
    if (width == 1)
    {
        return isArrayMixed;
    }

    for (int i = nx; i < nx + width; i++)
    {
        for (int j = ny; j < ny + width; j++)
        {
            if (arr[i][j] != arr[nx][ny])
            {
                isArrayMixed = true;
                return isArrayMixed;
            }
        }
    }

    return isArrayMixed;
}

void dfs(int cx, int cy, int node_num, int width)
{

    int new_width = width / 2;
    int nx, ny;
    for (int i = 0; i < 4; i++)
    {
        nx = cx + (dx[i] * new_width);
        ny = cy + (dy[i] * new_width);

        node new_node;
        if (!isMixed(nx, ny, new_width))
        { // 0과 1로만 이루어져있으면
            new_node.data = arr[nx][ny];
            new_node.node_num = -1;
            tree[node_num].push_back(new_node);
        }
        else
        {
            new_node.data = -1;
            node_counter += 1;
            new_node.node_num = node_counter;
            tree[node_num].push_back(new_node);
            dfs(nx, ny, new_node.node_num, new_width);
        }
    }
}

void dfs2(int index)
{
    cout << "(";
    for (int i = 0; i < tree[index].size(); i++)
    {
        if (tree[index][i].node_num == -1)
        {
            cout << tree[index][i].data;
        }
        else
        {
            dfs2(tree[index][i].node_num);
        }
    }
    cout << ")";
}

int main()
{
    string str;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> str;
        for (int j = 0; j < str.size(); j++)
        {
            arr[i][j] = str[j] - '0';
        }
    }

    if (!isMixed(0, 0, N))
    {
        cout << arr[0][0];
    }
    else
    {
        node_counter = 0;
        dfs(0, 0, 0, N);

        dfs2(0);
    }
}