[백준/BOJ] 백준 코딩 알고리즘 2447번 별 찍기 - 10/Python

문제

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

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

***
* *
***

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

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

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

예제 입력 1

27

예제 출력 1

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

 

풀이

분명 예전에 풀었음에도 불구하고, 다시 풀려고 하니까 도저히 생각이 안나서 다른 사람의 풀이를 참고했다 (https://cotak.tistory.com/38)

 

우선 코드는 다음과 같다

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(input())
print('\n'.join(append_star(N)))
print(len(append_star(N)))

 

하나씩 풀어서 테스트 케이스마다 생각해보면 다음과 같이 그릴 수 있다

 

n이 3인 경우의 테스트 케이스 풀이 시각화

1. 우선 n 값으로 3이 들어와 append_star 함수를 호출하고 인자로 3을 넘긴다

2. append_star(3) 은 3을 다시 3으로 나누어 append_star 함수를 호출한다 -> 재귀호출!

3. append_star(1) 은 if문을 통해 ['*']를 반환한다 -> 가장 작은 문제 단위!

4. 반환된 ['*']는 stars 변수에 저장된다

5. 윗줄, 가운데줄, 아랫줄을 for 문을 돌며 출력할 문자열을 L 리스트에 차례차례 추가한다

6. 윗줄: stars 리스트 변수에는 현재 값이 한 개 이기 때문에 루프를 한 번만 돌고, 해당 요소인 '*'를 3번 반복한 것을 L 리스트에 추가한다

7. 가운데줄: for loop의 아이템(해당 요소)인 '*'를 한 번 쓰고, 공백 길이를 계산하여 넣고, 다시 '*'를 한번 쓰고, 이를 L 리스트에 추가한다

8. 아랫줄: 윗줄과 동일한 작업을 거친다

9. L 리스트 변수에는 줄단위로 각 문자열이 저장되어 있고, 이를 메인 함수로 반환한다

10. 메인 함수에서는 반환받은 리스트를 각 문자열을 줄띄움 기호로 연결하여 출력하도록 한다

 

 

이 문제를 풀다보면 혼란스러운 부분이 가장 작은 문제단위가 '*' 인지 '***' 인지 헷갈리는 순간이 오게 되는데,

풀이를 따라가다 보면 사실상 가장 작은 문제 단위는 '*'인 것을 알 수 있다

 

 

동일하게 테스트케이스의 값이 9로 한 배수 더 커진 경우에는 다음과 같이 풀게 된다

 

얼핏보면 복잡해보이지만 앞서 수행한 n=3인 경우와 동일하게 처리됨을 알 수 있다

 

 

내가 이 문제를 풀지 못했던 이유는 다음과 같다

- 재귀 문제는 큰 문제를 작은 문제로 쪼개야 하는데, 작은 문제를 잘 쪼개지 못했다

- 작은 문제를 쪼개지 못하니까 어디서 stopping point를 줘야할 지 찾지 못했다

- 정답을 변수에 저장하지 않고, 한 번에 출력하게 알고리즘을 설계하고자 함으로써 더욱 사고가 꼬이게 되었다.

 

 

다음 재귀 문제를 풀 때는 문제를 어느 단위로 쪼개야 하는지 더 주의깊게 살펴보고 생각해보며 풀어야겠다