[백준-cpp] 1992. 쿼드트리

1. 문제핵심

• N x N 맵에서 0 또는 1로만 이루어진 인접한 집합들을 묶어서 출력해야 한다.
• 맵 전체를 먼저 탐색하고 0과 1이 섞여 있으면 탐색 범위를 1/2씩 줄이면서 0이나 1로만 이루어진 집합이 있을 때까지 탐색한다. -> 큰 문제를 하위 문제로 쪼갠다(분할정복 알고리즘)
• 4구역을 탐색하는 순서에 따라 재귀함수로 구현하거나 stack으로도 구현할 수 있음.

2. 재귀함수를 이용한 풀이

#include "bits/stdc++.h"

using namespace std;

int N;
char arr[70][70] = {'0'};

string solve(int y, int x, int width)
{
    if (width == 1)
        return string(1, arr[y][x]);

    char now = arr[y][x];
    string ans = "";

    for (int j = y; j < y + width; j++)
    {
        for (int i = x; i < x + width; i++)
        {
            if (now != arr[j][i])
            {
                ans += '(';
                ans += solve(y, x, width / 2);
                ans += solve(y, x + width / 2, width / 2);
                ans += solve(y + width / 2, x, width / 2);
                ans += solve(y + width / 2, x + width / 2, width / 2);
                ans += ')';

                return ans;
            }
        }
    }

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

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

    cin >> N;

    for (int j = 0; j < N; j++)
    {
        string input;
        cin >> input;

        for (int i = 0; i < N; i++)
            arr[j][i] = input[i];
    }

    cout << solve(0, 0, N) << '\n';

    return 0;
}

• 기저 사례를 고려하지 않아 의미없는 시간낭비를 많이 했다.
• 범위를 절반씩 줄여가며 탐색하는 것에만 신경쓰다보니 범위가 1이거나 압축가능한 경우 처리를 하지 않고 쿼드트리 로직에만 원인을 찾았다.
• 구현을 할 때 큰 로직을 먼저 구상하고 코드로 구현할 때는 기저사례부터 순차적으로 고려한 다음 최소/최대의 반례를 체크하는 습관을 들여야겠다.

3. 스택을 이용한 풀이

#include <bits/stdc++.h>

using namespace std;

int N;
char arr[65][65];

string solve(int y, int x, int w)
{
    string ret = "";
    stack<tuple<int, int, int, string>> s;
    s.push({y, x, w, ""});

    while (!s.empty())
    {
        auto [cy, cx, w, close] = s.top();
        char now = arr[cy][cx];
        s.pop();

        bool same = true;
        for (int j = cy; j < cy + w; j++)
        {
            for (int i = cx; i < cx + w; i++)
            {
                if (arr[j][i] != now)
                {
                    ret += "(";
                    s.push({cy + w / 2, cx + w / 2, w / 2, close + ")"});
                    s.push({cy + w / 2, cx, w / 2, ""});
                    s.push({cy, cx + w / 2, w / 2, ""});
                    s.push({cy, cx, w / 2, ""});
                    same = false;
                    break;
                }
            }
            if (!same)
                break;
        }

        if (same)
        {
            ret += now + close;
        }
    }

    return ret;
}

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

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        string input;
        cin >> input;

        for (int j = 0; j < N; j++)
        {
            arr[i][j] = input[j];
        }
    }

    cout << solve(0, 0, N) << '\n';

    return 0;
}

• 스택으로 구현할 때 가장 고민했던 부분은 ')' 닫는 괄호를 넣는 시점을 어떻게 구현해야 하는지였다.
• 스택의 요소에 닫는괄호에 해당하는 데이터를 string형식으로 넣고 제일 마지막 요소에만 close(기존에 있던 닫는괄호) + ")"를 넣어줬다.