재귀 패턴을 사용한 별 찍기

백준 온라인 저지 2447번 문제로, 프랙탈 도형처럼 작은 단위로 내려가면서 동일한 패턴이 반복되는 도형을 스케일에 따라서 출력하는 문제이다.

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

N=1 일 때 3×3의 기본 패턴을 출력한다. 이후 N이 커질 때마다 가로 세로가 각각 3배씩 커지면서 현재 패턴을 9번 반복하는 식이다. 기본적으로 재귀를 쓰겠지만, 접근방법은 사실 다양하다. 2차원 배열 혹은 1차원배열로 버퍼를 만들고 규칙에 따라 '*' 혹은 ' '를 채워넣고 이를 나중에 문자열의 형태로 출력하는 방법도 있을 것이다. (이런 풀이가 많은 것 같다.)

파이썬에서 문자열은 immutable(불변) 데이터 타입이다. 이 말은 문자열 객체는 리스트와 달리, 한 번 생성된 이후에는 그속의 개별 문자를 변경할 수 없다는 말이다. 따라서 리스트를 만들어서 비슷하게 채워넣고 이를 join 하는 방법이 있을 수 있다. 하지만 개인적으로는 이 문제에서는 이 방법이 그다지 효율적이지 못하다. N 회의 시행에서 가로 세로를 3등분한 9개의 조각에 대해 재귀 호출을 반복해야 하기 때문에 시간복잡도가 지수적이라는 문제가 있다. (물론 실질적으로 6단계 이상 부터는 화면에 찍을 수 있을까 싶지만…)

대신에 출력될 각 라인을 연결한 리스트를 리턴하는 함수를 작성하는 것으로 해보자. 이를 통해서 기본 패턴에 대해서 *이 출력될 위치에는 이전 레벨의 전체 데이터를, 공백이 출력될 위치에는 이전 레벨의 공백 데이터를 가져와서 라인단위로 조립하면 된다.

먼저, 채워져야 할 타일과 공백 타일의 기본 패턴은 다음과 같이 정의한다.

tile = ['***', '* *', '***']
spc = ['   '] * 3

간단하게 공백이 되는 부분을 만들어주는 함수를 보자.

from typing import List

def space(n: int) -> List(str):
  if n < 2:
    return spc
  xs = space(n - 1)
  # xs는 이전 단계의 공백 사각형으로 3^(n-1)개 원소를 갖는 리스트
  res: List[str] = []
  for _ in spc
    temp: List[List[str]] = [xs] * 3
    for i in range(len(xs)):
      res.append(''.join(temp[j][i] for j in range(3)))
  return res

제대로 동작하는지 살펴보려면, spc 패턴의 내용을 공백이 아닌 "###" 등으로 바꿔서 확인해본다.

print('\n'.join(space(2)))

이번에는 채워지는 칸을 표현할 fill() 함수를 구현할 차례이다. space() 함수에서 기본적인 구조가 모두 마련돼 있으므로 약간의 변형을 더하면 된다.

  1. 이전 단계의 fill()space()를 모두 호출해서 필요한 요소들을 준비한다.
  2. 기본패턴의 * 에 대해서는 fill()의 결과를, 공백에 대해서는 space()의 결과를 사용한다.
def fill(n: int) -> List[str]:
  if n < 2:
    return tile
  xs = fill(n - 1)
  ys = space(n - 1)
  res: List[str] = []
  for row in tile:
    temp: List[List[str]]
    temp = [xs if c == '*' else ys for c in row]
    for i in range(len(xs)):
      res.append(''.join(temp[j][i] for j in range(3)))
  return res

마찬가지로 테스트해보자. 사실 여기까지가 풀이의 끝이라 할 수 있다.

print('\n'.join(space(2)))

문제에서는 레벨이 아닌 도형의 크기를 입력받는다, 즉 27을 입력받으면 fill(3)의 결과를 출력하도록 한다. 입력의 범위가 제한되어 있으므로 사전을 만들어서 처리하면 되겠다.

ns = {n**3:n for n in range(1, 10)}
print('\n'.join(fill(ns[int(input())])))