백준 1922번 쿼드트리

백준 1922번 쿼드트리 문제이다.

 

문제는 다음과 같다. 

 

이번 문제도 이전 2630번 색종이 만들기, 1780번 종이의 개수 문제와 유사한 문제이다. 

다른점은 입력의 형식이 다르고 이전에는 종이의 개수를 구했다면 이 문제는 괄호와 0, 1을 이용한 문자열로 표현하는 것이다.

색종이 만들기와 같이 4분할을 하여 단계가 넘어가고 만약 모두 1이거나 모두 0이면 1, 0으로 표현 아니라면 4분면 각각을 숫자로 표현하는 방법이다 단계는 괄호로 구분해준다. 

 

코드는 다음과 같다.

import sys

ln = int(sys.stdin.readline().strip())
result = ''
arr = []


def check(n, x, y):
    global result
    for i in range(n):
        for j in range(n):
            if arr[x][y] != arr[x+i][y+j]:
                return 0
    if arr[x][y] == '0':
        result = result + '0'
    elif arr[x][y] == '1':
        result = result + '1'


def nemo(n, x, y):
    global result
    if n == 1:
        if arr[x][y] == '0':
            result = result + '0'
        elif arr[x][y] == '1':
            result = result + '1'
        return

    if check(n, x, y) == 0:
        result = result + '('
        for i in range(2):
            for j in range(2):
                nemo(n//2, i*n//2+x, j*n//2+y)
        result = result + ')'


for i in range(ln):
    arr.append(sys.stdin.readline().strip())


nemo(ln, 0, 0)
print(result)

 

이전 문제들과 로직은 비슷하며 입력값이 숫자가 붙어 나오는데 문자열로 받아 그대로 배열에 넣어주었고 이후 처리도 문자열로 처리했다.

추가로 출력값에 괄호가 있는데 이 괄호만 잘 신경써서 단계가 넘어갈때마다 추가되도록 넣어준다면 쉽게 풀린다.

 

성공!