백준 - 1992번(재귀,분할정복,쿼드트리)

바로 이전에 풀었던 2630번과 거의 동일한 문제이다.

핵심 아이디어는 정말 같고 추가되는 핵심 아이디어가 몇 개 있다.

분할된 사각형 마다 괄호( )를 사용해서 감싸 줘야 한다.

분할된 사각형은 재귀를 기준으로 나눌수 있다.

즉 재귀 직전에 '(' 를 삽입하고 재귀 끝난 직후에 ')'를 삽입하면 사각형 별로 연산을 묶을 수 있다.

 

팁)

1. print에서 원소 뒤에 sep='\n' 을 입력하면 리스트를 한 줄씩 볼 수 있다. 확인하면서 문제풀면 훨씬 수월하다.

2. sum(리스트명, []) 연산을 수행하면 2차원 리스트를 1차원으로 만들 수 있다.

3. 원소가 전부 1이거나 전부 0 일 땐 (1)이나 (0)이 아니라 반드시 1 혹은 0을 출력한다. (문제 잘 읽을 것)

4. 전부 1이거나 0이 아니라면 반드시 괄호 한 세트는 필요하므로 함수 호출 직전과 출력 직전에 각각 '('와 ')'을 넣고 시작할 것

 

import sys

n = int(sys.stdin.readline().strip())
arr = []
t_arr= []
for i in range(n):
    t_arr.append(sys.stdin.readline().strip())
    arr.append(list(map(str,str(t_arr[i]))))

ans = ['(']
def cut(arr):
    if len(arr[0]) > 1 and '0' in sum(arr,[]) and '1' in sum(arr,[]):
        a = len(arr[0]) / 2 #이전 사각형의 절반만큼으로 자르기
        a = int(a)
        temp1 = []
        temp2 = []
        temp3 = []
        temp4 = []

        for i in range(a): #사각형 4분할
            temp1.append(arr[i][:a])
            temp2.append(arr[i][a:])
            temp3.append(arr[i + a][:a])
            temp4.append(arr[i + a][a:])

        if '0' in sum(temp1,[]) and '1' in sum(temp1,[]):
            ans.append('(')
            cut(temp1)
            ans.append(')')
        else:
            if temp1[0][0] == '1':
                ans.append('1')
            else:
                ans.append('0')


        if '0' in sum(temp2,[]) and '1' in sum(temp2,[]):
            ans.append('(')
            cut(temp2)
            ans.append(')')
        else:
            if temp2[0][0] == '1':
                ans.append('1')
            else:
                ans.append('0')


        if '0' in sum(temp3,[]) and '1' in sum(temp3,[]):
            ans.append('(')
            cut(temp3)
            ans.append(')')
        else:
            if temp3[0][0] == '1':
                ans.append('1')
            else:
                ans.append('0')

        if '0' in sum(temp4,[]) and '1' in sum(temp4,[]):
            ans.append('(')
            cut(temp4)
            ans.append(')')
        else:
            if temp4[0][0] == '1':
                ans.append('1')

            else:
                ans.append('0')

    else:
        if arr[0][0] == '1':
            ans.append('1')
        else:
            ans.append('0')


cut(arr) #함수실행
ans.append(')')

if ans == ['(','1',')']:
    print(1)
elif ans == ['(','0',')']:
    print(0)
else:
    for i in ans:
        sys.stdout.write(i)