[C++] BOJ 1992번 - 쿼드트리

학교에서 진행하는 수업에서 알고리즘 문제를 공유받아 문제를 풀어보았다.

 

문제의 난이도는 실버 1로, 정답률은 약 60%이다. 시간 제한은 2초이다.

문제 링크

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

문제 설명

 이번 문제는 흑백 영상을 압축하는 문제이다. 주어진 영상이 모두 0으로 되어 있으면 "0"으로 압축이 되고, 1로 되어 있으면 "1"로 압축이 된다. 0과 1이 섞여있는 경우에는 좌상단, 우상단, 좌하단, 우하단으로 나누어 영상을 압축하게 되고, 압축한 결과를 괄호로 묶어 표현한다.

문제 분석

 문제에서 주어지는 입력인 비디오를 보면 문자열로 입력이 들어온다. 문제 해결을 위해 해당 문자열을 video[N][N] 배열로 매핑하는 과정이 필요하다.

 만약 비디오의 압축하고자 하는 영역의 값이 동일하지 않다면 좌상단, 좌하단, 우상단, 우하단으로 나뉘어진다는 점에서 재귀 함수로 문제를 해결할 수 있을 것으로 보인다.

자료 구조 및 알고리즘

재귀

 이번 문제는 재귀를 활용하여 풀기 적합한 문제이다. 좌상단, 우상단, 좌하단, 우하단으로 나뉘어지는 부분을 재귀를 통해 구현할 수 있다.

문제 풀이

 먼저 문제 해결에는 재귀 방식이 사용되었다. 함수는 다음과 같은 파라미터와 return 타입을 갖는다.

void func(int topX, int topY, int width);

 

 func 함수 내에서는 비디오의 값이 전체가 동일한지 확인하기 위해 전체를 for문으로 확인하고, 모든 값이 동일하면 hasDifferenceValue가 false, 동일하지 않으면 true가 되도록 구현하였다.

int value = video[topX][topY];
bool hasDifferentValue = false;
for (int i = topY; i < topY + width; i++)
{
    if (hasDifferentValue)
        break;
    for (int j = topX; j < topX + width; j++)
    {
        if (value != video[j][i])
        {
            hasDifferentValue = true;
            break;
        }
    }
}

 

만약 hasDifferenceValue의 값이 참이 되면

if (hasDifferentValue)
{
    cout << "(";
    func(topX, topY, width / 2);                         // 왼쪽 상단
    func(topX + width / 2, topY, width / 2);             // 오른쪽 상단
    func(topX, topY + width / 2, width / 2);             // 왼쪽 하단
    func(topX + width / 2, topY + width / 2, width / 2); // 오른쪽 하단
    cout << ")";
} 
else
{
    cout << value;
}

 

위 코드와 같이 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단으로 구분하여 재귀를 돌게 된다. hasDifferenceValue의 값이 거짓이면 압축된 값을 출력한다.

 

만약 재귀를 도는 과정에서 width의 값이 1이 된다면 값을 출력하고 바로 return한다.

if (width == 1)
{
    cout << video[topX][topY];
    return;
}

 

 

전체 코드는 아래와 같다.

전체 코드

#include <iostream>

using namespace std;

int video[65][65];

void func(int topX, int topY, int width)
{
    if (width == 1)
    {
        cout << video[topX][topY];
        return;
    }

    int value = video[topX][topY];
    bool hasDifferentValue = false;
    for (int i = topY; i < topY + width; i++)
    {
        if (hasDifferentValue)
            break;
        for (int j = topX; j < topX + width; j++)
        {
            if (value != video[j][i])
            {
                hasDifferentValue = true;
                break;
            }
        }
    }

    if (hasDifferentValue)
    {
        cout << "(";
        func(topX, topY, width / 2);                         // 왼쪽 상단
        func(topX + width / 2, topY, width / 2);             // 오른쪽 상단
        func(topX, topY + width / 2, width / 2);             // 왼쪽 하단
        func(topX + width / 2, topY + width / 2, width / 2); // 오른쪽 하단
        cout << ")";
    }
    else
    {
        cout << value;
    }
}

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

    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        string input;
        cin >> input;
        for (int j = 0; j < N; j++)
        {
            video[j][i] = input[j] - '0';
        }
    }

    func(0, 0, N);

    return 0;
}