[분할정복/DQ] 백준 1992 쿼드트리 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1992번: 쿼드트리

 

 

 

2. 문제 풀이

 영상 압축방법인 쿼드 트리를 구현하는 문제입니다.

 

2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

[Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

 해당 영역이 모두 0이면 0, 1이면 1을 출력하고 섞여있으면 4분할로 나누어서 판별하는 분할정복 문제입니다. 모두 0 혹은 1이면 그대로 출력하면 되고, 4분할할 때만 '(' 1사분면 + 2사분면 + 3사분면 + 4사분면 ')' 결과를 출력하면 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#입력
N = int(input())
video = []
for _ in range(N):
    video.append(list(map(int, input().rstrip())))

#분할정복(x, y, 입력크기)
def quadTree(x, y, n):
    #모든 영역이 0 혹은 1
    if x := isSame(x, y, n):
        return str(x-1)

    #4분할로 분리
    else:
        return '('+quadTree(x, y, n//2)+quadTree(x, y+n//2, n//2)+quadTree(x+n//2, y, n//2)+quadTree(x+n//2, y+n//2, n//2) +')'

#영역확인 (x, y, 입력크기)
def isSame(x, y, n):
    pixelSum = 0
    for i in range(x, x+n):
        for j in range(y, y+n):
            pixelSum += video[i][j]

    if pixelSum == n*n: #전부 1
        print(f"{n}크기: {pixelSum}, ({y+1}, {x+1}) => 1")
        return 2
    elif pixelSum == 0: #전부 0
        print(f"{n}크기: {pixelSum}, ({y+1}, {x+1}) => 0")
        return 1
    else: #섞임
        print(f"{n}크기: {pixelSum}, ({y+1}, {x+1}) => 4분할")
        return 0

print(quadTree(0, 0, N))

 본래 판별함수와 분할함수를 나누어서 구현했으나, 자꾸 순서가 뒤바뀌는 경우가 있어 하나로 통합했습니다.

 

 

import sys
input = sys.stdin.readline

# 입력
N = int(input())
video = []
for _ in range(N):
    video.append(list(map(int, input().rstrip())))


# 분할정복(x, y, 입력크기)
def quadTree(x, y, n):
    for i in range(x, x + n):
        for j in range(y, y + n):
            # 같지 않으면 4분할
            if video[x][y] != video[i][j]:
                return '(' + quadTree(x, y, n // 2) + quadTree(x, y + n // 2, n // 2) + quadTree(x + n // 2, y, n // 2) + quadTree(x + n // 2, y + n // 2, n // 2) + ')'
    #모두 같으면 출력
    return str(video[x][y])

print(quadTree(0, 0, N))

 위 코드는 통합버전입니다.