백준 1992 파이썬 | 쿼드트리

코드

n = int(input())
lst = []
for _ in range(n):
    lst.append(list(map(int, input())))

def quad(x, y, N):
    one = lst[x][y]
    for i in range(x, x+N):
        for j in range(y, y+N):
            if one != lst[i][j]:
                print("(", end="")
                quad(x, y, N//2)
                quad(x, y+N//2, N//2)
                quad(x+N//2, y, N//2)
                quad(x+N//2, y+N//2, N//2)
                print(")", end="")
                return
    if one == 0:
        print(0, end="")
    else:
        print(1, end="")

quad(0, 0, len(lst))

설명

https://con2joa.tistory.com/25

백준 2630 파이썬 | 색종이 만들기

이걸로 푼 문제와 거의 유사하다. 아니 그냥 똑같다. 오랜만에 다시 푸니까 못 풀었다. 다 잊어버렸나보다. 접근은 비슷하게 했는데 코드를 제대로 구현하지는 못 했다.

 

문제 이름에서 알 수 있듯이 쿼드트리를 이용하는 문제이다. 문제 해결을 위해 색종이 만들기 문제의 틀을 그대로 따왔다. 색종이 만들기 문제와 다른 점은 quad() 함수 안에서 print 를 작성해줘야 하는 부분이다.

 

쿼드트리 알고리즘을 기억하려면 함수의 인자로 x, y, n 을 쓰는 걸 기억하면 좋겠다.

 

메모리: 29452 KB

시간: 76 ms

 

문제

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

1992번: 쿼드트리