[백준/Python] 10994 별 찍기- 19

문제: https://www.acmicpc.net/problem/10994

 

 

입력

• 1 <= N <= 100

 

사용 알고리즘: 재귀

 

 

예제를 보고 규칙을 유추한 뒤 별을 찍는 문제

네모 안에 네모 안에 네모.. -> 재귀를 이용해서 풀어야겠다

 

 

예제 입력1

1

 

예제 출력1

*

 

예제 입력2

2

 

예제 출력2

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

 

예제 입력3

3

 

예제 출력3

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

 

예제 입력4

4

 

예제 출력4

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

 

 

구현

 

가장 큰 네모를 먼저 그리고 -> 그 다음 큰 네모 -> 그 다음 큰 네모 -> ...

 

1. 이차원 리스트를 만들어두고 for 문을 돌면서 별을 찍어야 하는 곳에 1을 넣음 (네모 그리기)

2. 네모를 다 그렸다면, 그 다음 큰 네모 모양을 만들기 위해 다시 함수 호출

3. n == 1 이 되면 제일 작은 네모까지 도달한 것이므로 제일 작은 네모(*) 를 그리고 리턴

 

 

네모 그리기 함수 (별 찍기)

 

계속해서 작은 네모를 그리기 위한 재귀함수

- start: 네모 시작 인덱스

- end: 네모 끝나는 인덱스

def func(n, start, end):
    if n == 1: # 베이스케이스, 제일 작은 네모(*) 그리고 리턴
        arr[start][start] = 1
    else:
        for i in range(start, end+1):
            for j in range(start, end+1):
                if i == start or i == end: # 맨위, 맨아래 줄
                    arr[i][j] = 1
                else:
                    if j == start or j == end: # 세로 줄
                        arr[i][j] = 1
        func(n-1, start+2, end-2) # 네모 그리기가 끝나면 함수 호출

 

 

출력

for i in range(x):
    for j in range(x):
        if arr[i][j]: # 배열의 값이 1이면 * 출력
            print('*', end='')
        else: # 배열의 값이 0 이면 ' ' 출력
            print(' ', end='')
    print()

 

 

 

전체 코드

# 네모 그리기(별 찍기) 함수
def func(n, start, end):
    if n == 1:
        arr[start][start] = 1
    else:
        for i in range(start, end+1):
            for j in range(start, end+1):
                if i == start or i == end:
                    arr[i][j] = 1
                else:
                    if j == start or j == end:
                        arr[i][j] = 1
        func(n-1, start+2, end-2)

# 입력
n = int(input())
x = 4 * (n-1) + 1

# 이차원 배열 초기화
arr = [[0] * x for _ in range(x)]

# 함수 실행
func(n, 0, 4*(n-1))

# 출력
for i in range(x):
    for j in range(x):
        if arr[i][j]:
            print('*', end='')
        else:
            print(' ', end='')
    print()