백준 파이썬 9097번

Urchinode·2022년 2월 16일

백준 분할정복 알고리즘

PS

목록 보기

6/14

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

분할정복을 연습하기 위해 푼 문제.

분할정복

다음의 과정을 거쳐 분할정복을 수행한다.

Divide: 큰 문제를 작은 문제로 쪼갠다(Recursion call). 단, 유형이 비슷해야 한다.

Conquer: 쪼개진 작은 문제들을 재귀적으로 해결한다. 간단하게 해결할 수 있을 정도로 충분히 작은 문제는 쪼개지 않고 즉각 해결한다.

Combine: Subproblem의 답을 합쳐 원래 문제를 해결한다.

간단하게 해결할 수 있는 크기와 해결 방법(Base case),
재귀 호출이 필요한 조건과 시기를 알아내는 것이 설계 과정에서 중요하다고 느꼈다.

9097번을 해결하기 전에 1992번을 먼저 해결했는데,
분할정복을 연습하기 좋았다.
https://www.acmicpc.net/problem/1992

9097번 역시 Image Compression 문제이고 분할정복으로 해결했다.
이 문제의 경우, 재귀호출이 필요한 상황일 때, 즉시 재귀호출을 하면 안 된다고 느꼈다.
Recursion Tree에서 현재 Level을 전부 해결하고 다음 Level을 진행해야 하기 때문이다.
현재 Level 중 어떤 노드가 재귀호출이 필요해서 바로 재귀호출을 수행하면 현재 Level의 모든 노드를 해결하지 않고 다음 Level로 넘어가기 때문에 어렵다고 느꼈다.

result = str()

# To proceed recursion in order in terms of recursion tree level,
# Store the information of subproblem in stack
recursive_stack = []


def bitStream(arr):
    global result
    global recursive_stack
    while recursive_stack:
        x, y = recursive_stack[0][0], recursive_stack[0][1]
        n = recursive_stack[0][2]
        recursive_stack = recursive_stack[1:]

        # Base Case
        if n == 1:
            result += '0' + arr[x][y]
        else:
            if checkPixel(arr, n, x, y) == False:
                result += '1'
                recursive_stack.append([x, y, n // 2])
                recursive_stack.append([x, (2 * y + n) // 2, n // 2])
                recursive_stack.append([(2 * x + n) // 2, y, n // 2])
                recursive_stack.append([(2 * x + n) // 2, (2 * y + n) // 2, n // 2])
            else:
                result += '0' + arr[x][y]
        bitStream(arr)


# Check whether the recursion is needed or not
def checkPixel(arr: list, n: int, x: int, y: int) -> bool:
    for i in range(n):
        for j in range(n):
            if arr[x + i][y + j] != arr[x][y]:
                return False
    return True


T = int(input())
while T:
    N = int(input())
    arr = [list(map(str, input().split())) for _ in range(N)]
    recursive_stack.append([0, 0, N])
    bitStream(arr)

    # Convert binary to hex
    result = format(int(result, 2), 'X')
    print(result)
    result = str()
    T -= 1