#2447. 별 찍기

유형: 재귀함수
작성일시: 11월 12일

📖문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

N (N⇒ $3^k$, 1≤k≤8)

27

출력

첫째 줄부터 N번째 줄까지 별을 출력

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

---

🔍분석

1. 패턴 찾기

1) N = $3^1$일 때를 생각해본다

# N = 3
***
* *
***

2) N = $3^2$일 때의 패턴을 생각해본다.

• 가운데에 3X3의 공백이 있다.
• N = 3일때의 패턴이 연속된다.

# N = 9
*********
* ** ** *
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

3) 일반적인 N = 3^i일 때를 생각해본다.

2. 함수 호출 순서와 실행순서

• 함수 호출 순서 : R(27) → R(9) → R(3)
• 함수 실행 순서 : R(3) → R(9) → R(27)
  

풀이(정답)

출처 : [백준] 2447 - 별 찍기 - 10 [Python(파이썬)]

1번재 방법

• 별을 9개의 공간으로 나눈 뒤 1번 공간의 별이 5번 공간을 제외한 나머지 공간의 별에 똑같이 복사한다.

import sys
sys.setrecursionlimit(10**6)

def paint_star(LEN):
    DIV3 = LEN//3
    if LEN == 3:
        g[1] = ['*', ' ', '*']
        g[0][:3] = g[2][:3] = ['*']*3
        return
   
    paint_star(DIV3)

    for i in range(0, LEN, DIV3):
        for j in range(0, LEN, DIV3):
            if i != DIV3 or j != DIV3:
                for k in range(DIV3):
                    g[i+k][j:j+DIV3] = g[k][:DIV3]

n = int(sys.stdin.readline().strip())
g = [[' ' for _ in range(n)] for _ in range(n)]

paint_star(n)

for i in range(n):
    for j in range(n):
        print(g[i][j], end='')
    print()

2번째 방법

• 공간을 1, 2, 3으로 나눈 후 재귀함수를 통해 구해진 별을 붙인다.(append)
• 1번 풀이에 비해 직관적이며 속도 빠름

import sys
sys.setrecursionlimit(10**6)

def append_star(LEN):
    if LEN == 1:
        return ['*']

    Stars = append_star(LEN//3) 
    L = []  
   
    for S in Stars:
        L.append(S*3)
    for S in Stars:
        L.append(S+' '*(LEN//3)+S)
    for S in Stars:
        L.append(S*3)
    return L

n = int(sys.stdin.readline().strip())
print('\n'.join(append_star(n)))

💡나의 풀이과정

나중에 알게 되었지만 나는 2번 풀이대로 문제를 풀었다!

답을 모른 채로 풀어서, 조금은 산만하지만 점차 다듬어갔다.
그리고 완성되지 않았다... 그냥 !!! 일단 올리는 거 먼저 할 거다ㅜ

1번째 시도 : 3X3 먼저 생각해보기

for i in n:
	for j in n:
		if i==1 and j==1:
			print(" ")
		print("*")
	print("\n")

→ 문제 발생

함수 내부에서는 print 하지 않는다.

재귀함수 형태로 바꿔준다.

줄 바꿈을 해야 하기 때문에, matrix를 설정하고, 함수 밖에서 print해야 한다.

2번째 시도

def star(n):
	if n == 1: 
		return ['*']
	star(n / 3): # star(27) -> star(9) -> star(3)
	s = n/3
	starlist = ['***', '* *', '***']
	for i in range s :
		starlist.append(' ')
	for i in range s :
			starlist.append(' ')
	for i in range s : 
			starlist.append(' ')

n= int(input) #입력	

print(star(n))#호출

3번째 시도

def star(n):
	if n == 1: 
		return ['*']
	#starlist = ['***', '* *', '***']
	s = int(n / 3) # n=3 -> s = 1, s=3
	a = star(s) # a = ['*'] [['***'], ['* *'], ['***']]
	for i in range a :
		starlist.append(i * 3) #-> ['*' '*', '*']
	for i in range a :
		starlist.append(i+ ' ' * s + i) # ['*', ' ', '*']
	for i in range a : 
		starlist.append(i*3) #-> [‘*’ ‘*’, ‘*’]
return starlist  [['***'], ['* *'], ['***']]

---

🤔회고

• 재귀.. 개념은 쉬운데 코드로 하면 여전히 어렵다. 사실 이 때도 제대로 이해를 못하고 얼렁뚱땅 넘어갔는데, 지금은 더 이해가 안 된다… 이렇게 뒤늦게라도 복습해서 다행이라 생각한다.
• 재귀함수의 개념은 이 문제를 통해서 조금 더 제대로 이해할 수 있게 된 것 같다…!