165. 1992(쿼드트리) - 파이썬

import sys
input = sys.stdin.readline

N = int(input())
paper = [list(map(int, input().rstrip())) for _ in range(N)]

result = []


def find(x, y, N):
    color = paper[x][y]
    for i in range(x, x+N):
        for j in range(y, y+N):
            if color != paper[i][j]:
                result.append(str("("))
                find(x, y, N//2)
                find(x, y+N//2, N//2)
                find(x+N//2, y, N//2)
                find(x+N//2, y+N//2, N//2)
                result.append(str(")"))
                return
    if color == 0:
        result.append(str(0))
    else:
        result.append(str(1))


find(0, 0, N)
print("".join(result))

문제요약

각 4개의 각 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현하라.

설명

분할정복에 대해서는 아래를 참고하자.

https://smhope.tistory.com/432?category=1056187 

[알고리즘 | 자료구조] 분할정복

이 문제는 아래 문제와 크게 다르지 않다.

https://smhope.tistory.com/434

164. 2630 (색종이 만들기) - 파이썬

똑같이 4개의 영역을 나누고, N*N의 온전한 사각형이 만들어 지면 그 값을 하나의 온전한 사각형으로 생각한다.

                find(x, y, N//2)
                find(x, y+N//2, N//2)
                find(x+N//2, y, N//2)
                find(x+N//2, y+N//2, N//2)

각 1사분면,2사분면,3사분면,4사분면으로 하여 처리할 것이다.

처리가 시작하면 괄호를 열어야 한다. 때문에 아래 코드를 추가해줄것이다.

                result.append(str("("))

또한 처리가 끝나면 괄호를 닫아주어야 하므로 다음코드도 추가된다.

                result.append(str(")"))

이를 합치면 다음과 같아진다.

                result.append(str("("))
                find(x, y, N//2)
                find(x, y+N//2, N//2)
                find(x+N//2, y, N//2)
                find(x+N//2, y+N//2, N//2)
                result.append(str(")"))