백준 1992 쿼드 트리 문제풀이 (Python)

백준 1992 쿼드 트리 문제입니다.

 

파악해야 하는 사각형 범위가 모두 0으로 되어 있거나 1로 되어있다면 해당 숫자를 출력하고

 

그렇지 않다면 재귀를 타고 가면서 동일한 과정을 반복하는 문제입니다.

 

N이 64밖에 되지 않으므로 O(N**2) 으로도 문제를 해결할 수 있습니다.

 

저는 분할 정복 방식으로 문제를 해결하였습니다.

 

제가 작성한 코드는 다음과 같습니다.

 

N = int(input())
arr = []
for i in range(N):
    arr.append([])
    temp = list(str(input()))
    for j in range(N):
        arr[i].append(int(temp[j]))


def div_logic(tx, ty, length):
    next_length = length // 2
    print("(", end="")
    div_and_conquer(tx, ty, next_length)
    div_and_conquer(tx, ty + next_length, next_length)
    div_and_conquer(tx + next_length, ty, next_length)
    div_and_conquer(tx + next_length, ty + next_length, next_length)
    print(")", end="")


def div_and_conquer(tx, ty, length):
    s = 0
    for i in range(tx, tx + length):
        for j in range(ty, ty + length):
            s += arr[i][j]
    if s == 0:
        print(0, end="")
    elif s == length ** 2:
        print(1, end="")
    else:
        div_logic(tx, ty, length)


if __name__ == '__main__':
    div_and_conquer(0, 0, N)

 

출처

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

1992번: 쿼드트리