백준 1992 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

분할 정복의 기초라고 볼 수 있는 문제다. 

분할 정복이란 어떤 일정한 규칙 또는 반복된 연산이 적용되는 정점 또는 상황 들을 여러 개로 나누어(분할) 빠르게 처리하고 다시 합쳐주는 (정복) 풀이 방식이라고 할 수 있다. 여기서 중요한 부분은 바로 '합치기가 가능한가?'이다. 이전 포스팅(행렬 곱셈 순서)에서도 보았듯이, 나누고 합치기를 할 때 적용되는 어떠한 규칙 등이 있어야 한다. 이 문제에서는 양 옆에 괄호를 붙이는 것이 그 규칙이라 말할 수 있다.

 

계속 범위를 4 분하여 줄여나가기 위한 재귀 함수가 필요할 것이고,

그 함수 각각의 내부에서 4분하여 더욱 작아진 면적이 다음 재귀 함수 내부로 들어가는 구조를 갖게 된다. 

그리고 각 재귀함수의 리턴을 모아서 괄호를 양 끝에 붙인 후, 윗 단계로 올려주면 다시 리턴해주면 된다.

 

파이썬 코드를 예시로 살펴보겠다.

img1 = [[0 for _ in range(sz//2)]for _ in range(sz//2)]
img2 = copy.deepcopy(img1)
img3 = copy.deepcopy(img1)
img4 = copy.deepcopy(img1)

위와 같이 주어진 영상 정보를 나누기 위한 4개의 분할 면적을 만든다 (img1 ~ 4). 이러한 면적 4 분할은 각 재귀 함수 내에서 매번 행해져야 한다. 그 면적이 1이 될 때까지! 그것이 바로 재귀 함수의 기저 조건(탈출 조건)이 된다. 

return '('+quadtree(img1)+quadtree(img2)+quadtree(img3)+quadtree(img4)+')'

그리고 위와 같이 나눠진 면적들이 재귀함수 내부로 모두 들어가고, (루프를 통해서 간략하게 표현할 수도 있다) 각각의 리턴을 모아 양옆에 괄호를 붙여 리턴해주게 된다.

 

<주요 내용>

분할 정복, 기저조건(탈출조건), 재귀 함수, 쿼드 트리

 

<코드>

 

# dont have to create 4 2-d arrays everytime inside quadtree

import sys
import copy
si = sys.stdin.readline


def quadtree(img):
    if len(img) == 1:
        return str(img[0][0])
    sz, s = len(img), 0
    img1 = [[0 for _ in range(sz//2)]for _ in range(sz//2)]
    img2 = copy.deepcopy(img1)
    img3 = copy.deepcopy(img1)
    img4 = copy.deepcopy(img1)

    for i in range(sz):
        for j in range(sz):
            s += img[i][j]
            if i < sz//2 and j < sz//2:
                img1[i][j] = img[i][j]
            if i < sz//2 and j >= sz//2:
                img2[i][j-sz//2] = img[i][j]
            if i >= sz//2 and j < sz//2:
                img3[i-sz//2][j] = img[i][j]
            if i >= sz//2 and j >= sz//2:
                img4[i-sz//2][j-sz//2] = img[i][j]

    if s == sz*sz:
        return '1'
    if not s:
        return '0'
    return '('+quadtree(img1)+quadtree(img2)+quadtree(img3)+quadtree(img4)+')'


def main():
    n = int(si())
    img = []
    for _ in range(n):
        l = [int(e) for e in si().strip()]
        img.append(l)
    print(quadtree(img))


if __name__ == '__main__':
    main()

 

아래는 C++버전이다.

string으로 받아 substr메서드를 통해 4 분하였다. 

sDiv함수는 4개로 나눠주는 함수이고, sDet함수는 0인지 1인지를 판단하며, DnC는 Divide and Conquer의 약자로서, 분할 정복을 행하는 함수이다. 

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

int n;
string ans;
char sDet(string *s, int n);
void sDiv(string *s, int n);
void DnC(string *s, int n);

int main()
{
    int n;
    cin >> n;
    if (n == 1)
    {
        char sAns;
        cin >> sAns;
        cout << sAns << '\n';
        return 0;
    }
    string s[n];
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    char temp = sDet(s, n);
    if (temp == '-')
        DnC(s, n);
    else
        ans += temp;
    cout << ans << '\n';
    return 0;
}

char sDet(string *s, int n)
{
    char t = s[0].at(0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (s[i].at(j) != t)
                return '-';
        }
    }
    return t;
}
void sDiv(string *s, int n)
{
    n /= 2;
    string s1[n];
    string s2[n];
    string s3[n];
    string s4[n];
    for (int i = 0; i < n; i++)
    {
        s1[i] = s[i].substr(0, n);
        s2[i] = s[i].substr(n, n);
        s3[i] = s[n + i].substr(0, n);
        s4[i] = s[n + i].substr(n, n);
    }
    char d = '-';
    char s1ans = sDet(s1, n);
    char s2ans = sDet(s2, n);
    char s3ans = sDet(s3, n);
    char s4ans = sDet(s4, n);
    if (s1ans == d)
        DnC(s1, n);
    else
        ans += s1ans;
    if (s2ans == d)
        DnC(s2, n);
    else
        ans += s2ans;
    if (s3ans == d)
        DnC(s3, n);
    else
        ans += s3ans;
    if (s4ans == d)
        DnC(s4, n);
    else
        ans += s4ans;
}
void DnC(string *s, int n)
{
    ans += "(";
    sDiv(s, n);
    ans += ")";
}