[백준/Python] 2447: 별 찍기 - 10

2447번: 별 찍기 - 10

문제

입력으로 3의 거듭제곱인 N이 주어질 때 N x N의 프랙탈 패턴을 출력하는 문제이다. 

주어진 패턴을 보면 N = 3일 때의 패턴이 크기가 커지며 반복되고 있다는 것을 알 수 있다. 이는 가운데 부분이 뚫려 있는 네모난 도넛 모양을 이루고 있다. 자세히 보면 N = 9일 때는 N = 3일 때의 패턴을 8개 가져다 놓은 모양이다. 그리고 N = 27일 때는 N = 9일 때의 패턴을 8개 가져다 놓았다. 즉 N = 3^x의 패턴은 N = 3^{x-1}의 패턴을 8개 복사한 모양을 이룬다.

 

이를 재귀함수로 구현하기 위한 로직은 다음과 같다.

 

1. Base case로 n == 3일 때 3 x 3의 패턴을 리턴하도록 한다.
2. 만약 n이 3보다 클 경우 재귀함수를 호출하여 3^{n-1}의 패턴을 가져온다. 
3. 이전 패턴을 불러왔다면 그 패턴을 가운데 부분을 제외하고 8개 붙여놓는다.

 

소스코드

import sys

def draw_pattern(n):
    if n == 3:
        pattern = ["***", "* *", "***"]
    else:
        prev_pattern = draw_pattern(n // 3)
        size = n // 3
        pattern = []
        
        # 상단부
        for r in prev_pattern:
            pattern.append(r * 3)
        
        # 중간부 (가운데 공백 포함)
        for r in prev_pattern:
            pattern.append(r + " " * size + r)
        
        # 하단부
        for r in prev_pattern:
            pattern.append(r * 3)
    
    return pattern

n = int(sys.stdin.readline())

pattern = draw_pattern(n)
for i in pattern:
    print(i)