[백준] 1992번 파이썬

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

문제 해결 방법

1. 1074, 2630번 문제와 거의 유사한 문제다. 이미지를 계속 4등분하여 1 또는 0만 가지는 정사각형 범위를 계속해서 찾는다.
2. 재귀 함수 호출로 탐색하기 시작할 때 각 탐색 단계의 결과를 괄호로 감싸 주어야 하기에 시작과 끝에 괄호를 닫아준다.
3. global 변수를 사용했는데, 2630번의 경우 answer가 리스트로 되어있다. 리스트는 인덱스에 주소를 담고 있다. 즉 리스트의 인덱스 0번에는 값이 아닌 주소가 들어 있어 재귀 함수 내에서도 주소를 통해 해당 변수에 접근할 수 있지만 이 문제에서 answer은 변수다. 따라서 global 변수로 선언해줘야 재귀 함수 내에서도 해당 변수를 사용할 수 있다.

import sys
input = sys.stdin.readline

N = int(input())
IMAGE = [input().strip() for _ in range(N)]
answer = ""


def comp(x, y, N):
    check = IMAGE[x][y]
    global answer
    for row in range(x, x + N):
        for col in range(y, y + N):
            if check != IMAGE[row][col]:
                answer += '('
                # 1사분면
                comp(x, y, N // 2)
                # 2사분면
                comp(x, y + N // 2 , N // 2)
                # 3사분면
                comp(x + N // 2, y , N // 2)
                # 4사분면
                comp(x + N // 2, y + N // 2, N // 2)
                answer += ')'
                return None
    if check == '0':
        answer += '0'
    else:
        answer += '1'
    return None


comp(0, 0, N)
print(answer)