TIL) 1992 쿼드 트리

이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

👩‍💻 쿼드 트리

Week02 TEST 첫 번째 문제
백준 1992 쿼드트리 : https://www.acmicpc.net/problem/1992

💡 아이디어

• 1780 종이의 개수 문제와 비슷한 분할정복 문제이다. 풀이도 거의 같다.
• size를 2로 나누면서 재귀 함수를 이용해 점점 더 작은 사각형을 검사한다.
• 첫번째 값을 저장한 후 그 값과 다른 값이 나오면 break를 해주면 전체 범위를 다 검사하지 않아도 된다.

🎡 제출한 코드

# 쿼드 트리
import sys

N = int(sys.stdin.readline())
pos = []
for _ in range(N):
    pos.append(list(map(int, sys.stdin.readline().strip())))


# 분할정복
def divide(x, y, size):
    type = pos[y][x]
    flag = False #

    for i in range(x, x+size):
        if flag == True:
            break
        for j in range(y, y+size):
            # type과 다른 숫자가 있을 때
            if pos[j][i] != type:
                print('(', end='')
                divide(x, y, size//2)
                divide(x+size//2, y, size//2)
                divide(x, y+size//2, size//2)
                divide(x+size//2, y+size//2, size//2)

                print(')', end='')
                flag = True
                break

    # 사이즈 안에서 type과 다른 숫자가 없었을 때
    if flag == False:
        if type == 1:
            print(1, end='')
        elif type == 0:
            print(0, end='')

# main함수
divide(0, 0, N)