[백준] 1992번 쿼드트리 파이썬 풀이

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

1992번: 쿼드트리

---

1. 접근 방식

• 문제 해결 흐름을 대략적인 슈도 코드로 파악하자.

1. is compressible?
2. if so, print 1 or 0
3. else,
    a. print (
    b. split into 4
    c. then go back to 1
    d. print )

 

코드를 작성하기 전에 먼저 문제를 읽으며, 어떤 흐름으로 코드를 작성해야 하는지 정리했다.

가장 먼저 압축 가능 여부를 파악한 후, 압축 가능하다면 곧 바로 1 또는 0을 출력한다.

압축할 수 없다면, 먼저 괄호를 열고, 영상을 4등분하여 다시 압축 가능 여부를 파악하는 과정을 반복한다.

 

① 압축 시도 ② 안 되면 4등분

두 작업을 계속 반복하므로, 재귀로 접근하는 것이 적절하다고 판단했다.

 

 

• 압축 여부 파악 방법: 해당 사분면의 모든 숫자의 합이 0 또는 사분면의 원소 개수와 동일한가?

 

예를 들면, 만약 영상이 모두 0으로 되어 있다면 총 합은 0, 모두 1로 되어 있다면 총 합은 4 x 4 = 16이다. 그러나 위 영상은 총 합이 8이므로, 0과 1이 섞여 있는 영상임을 파악할 수 있다.

 

 

 

2. 정답 코드

def compress(r, c, length):
    _sum = 0
    for i in range(r, r + length):
        for j in range(c, c + length):
            _sum += video[i][j]

    if _sum == 0:
        return 0

    if _sum == length ** 2:
        return 1

    return -1


def solve(r, c, k):
    result = compress(r, c, k)

    if result > -1:
        print(result, end="")

    else:
        print("(", end="")
        length = k // 2

        solve(r, c, length)
        solve(r, c + length, length)
        solve(r + length, c, length)
        solve(r + length, c + length, length)

        print(")", end="")


n = int(input())
video = [list(map(int, list(input()))) for _ in range(n)]
solve(0, 0, n)