백준 1992 풀이 (쿼드트리, 파이썬)

저번에 풀었던 2630 색종이 만들기 문제랑 동일하다.

다만 조금 다른점은 스트링으로 만들어주고, 어떤 포맷을 추가해주어야한다.

백준 2630 풀이 (색종이 만들기, 쿼드트리, 분할정복, 파이썬)

위의 데이터를 "(0(0011)(0(0111)01)1)" 로 나타내야 하는데 순서는 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽 아래다.

1. 만약 통일되지 않은 배열인 경우 "(" ")"가 추가된다.

2. 만약 통일되지 않은 배열인 경우 4분면으로 나누어 통일되었는지 검사한다.

3. 만약 통일되어 있다면 통일되어 있는 수를 string으로 넘겨준다.

위의 과정을 재귀함수로 만들어 코딩해 주면 된다.

n = int(input())

def check(p):
    f = p[0][0]
    w = 0
    for i in range(len(p)):
        for j in p[i]:
            if f != j:
                w = 1
                break
        if w == 1:
            break
    if w == 1: # 통일되지 않음
        # 자르자~
        a = []
        b = []
        c = []
        d = []
        for i in range(len(p)//2):
            a.append(p[i][:len(p)//2])
            b.append(p[i][len(p)//2:])
        for i in range(len(p)//2,len(p)):
            c.append(p[i][:len(p)//2])
            d.append(p[i][len(p)//2:])
        return "("+check(a)+check(b)+check(c)+check(d)+")"
    else:
        return str(f)

p=[]
for _ in range(n):
    p.append(list(input()))

print(check(p))