1992 - 쿼드트리 [분할정복]

출처 : 백준 1992 쿼드트리

더 많은 문제들에 대한 Python3 풀이는 Github Repo에서 찾아볼 수 있다.

문제

이 문제는 분할정복으로 풀어야 하는 문제이다. 0과 1로 이뤄진 2차원 배열이 주어지고 이 배열을 압축해서 표현을 하는 것이 목표이다. 배열 전체가 0으로 이뤄지면 답은 0이 되는 것이고 배열 전체가 1로 이뤄지면 답은 1이 되는 것이다.

만약 주어진 배열 전체를 하나의 숫자로 표현을 하지 못하면 4등분을 하는 것이다. 4등분을 할 때 ‘(‘ 를 추가한다. 4등분 한 다음에 왼쪽 위부터 시계방향으로 조각난 배열이 다시 1로만 이뤄졌는지 혹은 0으로만 이뤄졌는지 확인한다. 순회가 끝났으면 ‘)’를 추가한다.

위 입력은 다 1 혹은 0으로만 이뤄지지 않았기 때문에 4등분을 하고 나서 ‘(‘를 추가 시킨다. 그러고 나서 왼쪽 위부터 다시 진행을 한다.

왼쪽위의 배열도 다 같은 숫자로 표현이 되지 않기 때문에 다시 4등분을 하고 ‘(‘ 를 추가한다.

다시 4등분된 배열의 왼쪽위는 1로만 이뤄졌기 때문에 1을 추가한다. 오른쪽 위도 1로만 이뤄졌기에 1 추가하고 왼쪽 밑도 0으로만 이뤄졌기에 0을 추가한다. 오른쪽 밑은 하나의 숫자로 표현되지 않기 때문에 다시 4등분을 한다.

이러한 방식으로 계속 4등분을 하다면 배열의 마지막까지 도달하게 되고 프로그램은 종료된다.
이렇게 동작하는 알고리즘은 재귀로 간편하게 구현할 수 있다.
Base 조건으로는 n == 1, 즉 element 하나만 남았으면 더 나눠지지 않기 때문에 바로 print를 한다.
그 다음에는 현재 주어진 위치에 있는 배열의 값과 나머지 배열과 같은지 확인한다. 만약 같다면 다 0 또는 1이라는 말이기 때문에 0 또는 1을 print한다. 하지만, 다른 숫자가 나오면 4등분을 한다.

풀이

# BOJ 1992 - 쿼드 트리 - 분할 정복
import sys
r = sys.stdin.readline


def decompose(n, y, x):
    # print(n, y, x)
    if n == 1:
        print(image[y][x], end="")
        return

    flag = True
    for i in range(y, y+n):
        if not flag:
            break
        for j in range(x, x+n):
            if image[i][j] != image[y][x]:
                flag = False
                break

    if flag:
        print(image[y][x], end="")
    else:
        decreased_n = n//2

        print("(", end="")
        decompose(decreased_n, y, x)
        decompose(decreased_n, y, x+decreased_n)
        decompose(decreased_n, y+decreased_n, x)
        decompose(decreased_n, y+decreased_n, x+decreased_n)
        print(")", end="")


N = int(r())
image = [list(r().strip()) for _ in range(N)]
decompose(N, 0, 0)