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

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

1992번: 쿼드트리

---

코드

#https://teching.tistory.com/

import sys
res = ""
def makeConftti(list):
    global res
    tmp = 0
    for line in list:
        tmp += sum(line)
    n = len(list)
    if tmp == n*n:
        res += "1"
        return
    elif tmp == 0:
        res += "0"
        return
    #가로 세로 쪼개기
    res += "("
    splitPaper1 =[]
    splitPaper2 =[]
    splitPaper3 =[]
    splitPaper4 =[]
    for i in range(n):
        if i <= n//2 - 1 :
            splitPaper1.append(list[i][:n // 2])
            splitPaper2.append(list[i][n // 2:])
        if i > n//2 - 1:
            splitPaper3.append(list[i][:n // 2])
            splitPaper4.append(list[i][n // 2:])
    makeConftti(splitPaper1)
    makeConftti(splitPaper2)
    makeConftti(splitPaper3)
    makeConftti(splitPaper4)
    res += ")"

n = int(sys.stdin.readline().rstrip())
input = []
for _ in range(n):
    input.append([int(i) for i in sys.stdin.readline().rstrip()])
makeConftti(input)
print(res)

해설

https://teching.tistory.com/116

백준 2630: 색종이 만들기 (파이썬)

위 문제와 거의 동일한 방법으로 만들었다.

다만 '('와 ')'가 언제 포함되어야 하는지 고민할 필요가 있었다.

고민한 결과 압축이 불가능 한경우(즉, 쪼개는 경우)에 추가했다.

이것만 주의하면 어렵지 않게 구현할 수 있었다.