[백준] 1992번 쿼드트리

💡문제접근

• 오른쪽 위(1사분면), 왼쪽 위(2사분면), 오른쪽 아래(4사분면), 왼쪽 아래(3사분면)
• (0, 0)부터 탐색을 시작하면 (2, 4)에서 처음으로 재귀 함수가 실행이 되는데 이 때 , (x, y)을 기준으로 절반씩 잘라서 탐색을 진행한다.
• 왼쪽 위는 그대로 (x, y)가 되고 오른쪽 위는 (x, y + N // 2), 왼쪽 아래는 (x + N // 2), 오른쪽 아래는 (x + N // 2, y + N // 2)가 된다.

💡코드(메모리 : 31256KB, 시간 : 48ms)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
image = []
for _ in range(N):
    image.append(list(input().strip()))

result = []
def recursive(x, y, N):
    # 기준값
    check = image[x][y]
    for i in range(x, x+N):
        for j in range(y, y+N):
            # 특정 사분면의 값이 통일되지 않은 경우
            if image[i][j] != check:
                result.append("(")
                recursive(x, y, N//2)               # 왼쪽 위
                recursive(x, y + N//2, N//2)        # 오른쪽 위
                recursive(x + N//2, y, N//2)        # 왼쪽 아래
                recursive(x + N//2, y + N//2, N//2) # 오른쪽 아래
                result.append(")")
                return result

    # 특정 사분면의 모든 점이 1인 경우
    if check == '1':
        result.append('1')

    # 특정 사분면의 모든 점이 0인 경우
    if check == '0':
        result.append('0')
    return result

answer = recursive(0, 0, N)
print(''.join(map(str, answer)))

💡소요시간 : 38m