백준 1992 - 쿼드트리

 

처음 든 생각

- 아까 복습한 색종이 만들기 문제랑 완전 판박이네

- 4개로 분할할 때에 추가적으로 괄호가 들어가야하네

- 모두 0/1일 때 결과를 리턴함으로서 재귀 리턴 조건을 맞춰주고

- 4개로 분할할 경우 괄호를 포함한 재귀함수를 리턴해야겠다.

 

나의 답

import sys
input = sys.stdin.readline
N = int(input())

arr = [list(input()) for _ in range(N) ]
def search(x,y,n):
    zero_count = 0
    for i in range(n):
        for j in range(n):
            
            if arr[x+i][y+j] == "0":
                zero_count += 1

    if zero_count == n*n:
        return "0"
    elif zero_count == 0:
        return "1"
    else:
        return f"({search(x,y,n//2)}{search(x,y+n//2,n//2)}{search(x+n//2,y,n//2)}{search(x+n//2,y+n//2,n//2)})"
    
print(search(0,0,N))

 

https://selfdevelopcampus.tistory.com/164

백준 2630 - 색종이 만들기

 

위의 풀이를 참고하면 사실상 구조는 거의 똑같다. 

 

안에 0의 개수를 세서 0의 개수가 탐색하고자하는 정사각형에 가득 차있으면 0을 리턴하고 0개일 경우 모두 1이라는 뜻이므로 1을 리턴한다. 나중에 괄호까지 포함해서 리턴해야하므로 문자열 자료형의 0과 1을 리턴하도록 했다. 

 

그 다음 만약 모두 0이나 1이 아니면 4개로 분할을 해야한다. 이 역시 위의 "색종이 만들기" 문제와 거의 똑같다.

 

분할하는 정사각형의 시작점을 매개변수로 받는 함수로 구성하여 시작점을 조절하는 방식으로 정사각형을 분할한다. 그리고 각각의 정사각형의 탐색결과를 모두 합쳐서 괄호 안에 넣어주면 된다.

 

색종이 만들기를 제대로 복습했는지 스스로 점검할 수 있었던 좋은 문제였다. 정사각형의 4분할 과정 한 번 더 점검하고 넘어가자.