[재귀] 2447번 별 찍기-10

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30 + a

1. 문제 설명

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

2447번: 별 찍기 - 10

2. 접근 방식

- 27x27 블록의 경우 9x9짜리 모양 9개로 만들 수 있다. (27블록)
- 9x9 블록의 경우 3x3짜리 모양 9개를 그릴 수 있다. (9블록)
- 3x3 블록의 경우 간단하게 구현할 수 있다.(3블록)3x3블록을 만들기 전까지 재귀로 들어온다고 가정한다.- 9블록은 1~9의 파트로 이루어져 있고, 5번째(가운데)를 제외하고는 전부다 3짜리 모양으로 채우면 된다. 
- 그리고 27블록도 마찬가지로 1~9의 파트로 이루어져 있고, 5번째(가운데)를 제외하고는 전부다 9짜리 모양으로 채우면 된다.

---

이를 다시 정리하자면 아래와 같다고 할 수 있다.

1. 3블록를 먼저 만들 수 있도록 재귀적으로 들어간다. (문제에서는 27호출 → 9호출 → 3호출)
2. 3으로 된 함수가 호출됐다면 return되어, 9호출로 넘어온다. (9 호출←3 호출)
3. 9호출에서 총 9개의 블록을 3으로 된 블록으로 채워야 한다. 여기서 가운데의 경우는 그냥 넘어가도록 조건을 설정해줘야 한다.
4. (핵심코드) 𝑛=3^𝑖 의 경우 가운데를 제외하고 8개 지역에 𝑛=3^(𝑖−1)블록이 동일하게 찍힌다. (즉, 9블록의 경우 3블록이 동일하게 찍힌다는 뜻)
5. 그렇게 9호출이 끝나면 27호출로 넘어간다. 27블록은 앞서 만들었던 9블록을 사용해서 만들어준다.

3. 코드

n = int(input())
square = [[" "]*n for _ in range(n)]
def pattern(n):
    if n == 3:
        square[0][:3] = ["*"]*3
        square[1][:3] = ["*", " ", "*"]
        square[2][:3] = ["*"]*3
        return
    
    n //= 3
    pattern(n)
    for i in range(3):
        for j in range(3):
            if i ==1 and j ==1:
                continue
            for k in range(n): # 행만 바꾸고, 열은 그대로 똑같이 출력
                square[(n*i)+k][(n*j):n*(j+1)] = square[k][:n]
pattern(n)
for i in square:
    for j in i:
        print(j, end="")
    print()ㅐ

4. 코멘트

- 별찍기라고 만만하게 봤지만, 문제가 꽤나 어려웠다. 코드의 구성과 흐름은 잘 구현했지만, 핵심적인 부분과 재귀를 끝까지 들어갔을 때 어떤 값을 리턴해줘야 할 지에 대해서 혼자 생각하기에는 어려움이 있는 것 같다. 아래의 두 부분을 제대로 찾지 못해 시간이 오래 걸렸던 것 같다.

• 3x3블록 값을 미리 설정해줘야 하는 부분
• (핵심코드) 𝑛=3^𝑖의 경우 가운데를 제외하고 8개 지역에 𝑛=3^(𝑖−1) 블록이 동일하게 찍히는 규칙

- 재귀를 만들 때 초기 규칙을 어떻게 설정할 지에 대해 생각해볼 수 있는 코드라고 생각한다. 다시 한 번 공부해도 좋을 것 같다.