별 찍기 재귀함수 - byeol jjiggi jaegwihamsu

[백준] 2447번 별찍기 문제 재귀 함수 이용해서 풀기

• 2022.01.27 01:01
• Algorithm

문제

재귀적인 패턴으로 별을 찍어 보자. 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=3^k 이며, 이때 1 <= k < 8 이다.

출력

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

예제 입력 1

27

예제 출력 1

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

문제 풀이

우선, 규칙을 찾아보고 아이디어를 생각해 보자.

• n = 3^1 일때, 다음과 같이 별이 찍힌다.

• 일반항을 세워, n = 3^i 에 대하여 생각해 보자.

n = 3^1일때 가운데를 비워두고 별이 찍힌 것처럼,
n = 3^i 일때는 가운데를 비우고, n = 3^(i-1)일 때의 별 배열이 찍힌다.

이것이 이 문제를 풀이하는 데에 사용된 방법론이다.
이것을 이해하는 것이 핵심이다.

즉, n이 만약에 27이면, 재귀 함수를 이용하여 n이 3일때 재귀호출을 종료시키고,
n이 3일때의 배열로  n이 9인 배열을 만들고, n이 9인 배열로 n이 27일때의 배열을 완성시키면 된다.

문제 풀이 코드

def star(n):
    global map # global을  이용하여 map이라는 변수를 전역 변수로 지정해줌

    if n == 3:
        map[0][:3] = map[2][:3] = [1]*3
        map[1][:3] = [1, 0, 1]
        return

    a = n//3
    star(n//3)
    for i in range(3):
        for j in range(3):
            if i == 1 and j == 1:
                continue
            for k in range(a):
                map[a*i+k][a*j:a*(j+1)] = map[k][:a] # 가장 핵심인 부분이고, 이 풀이법이 지금으로서는 가장 우아한 풀이법 같다고 판단함.


    # print(map)


n = int(input())
map = [[0 for i in range(n)] for i in range(n)]
star(n)

for i in range(len(map)):
    for j in range(len(map[0])):
        if map[i][j] == 1:
            print('*', end = '')
        else:
            print(' ', end = '')
    print()

핵심 라인

map[a*i+k][a*j:a*(j+1)] = map[k][:a]

n = 9 이면, map의 배열이 해당 코드를 통해 아래와 같은 방식으로 배열이 삽입된다. (문제 풀면서 막 그린거라 좀 지저분..그래도 이해하는데에 도움이 되길..)

n = 3 일 때, map의 배열이 [[1, 1, 1],[1, 0, 1], [1, 1, 1]] 인데,
위 그림은 n=9 인 경우이다.
위 그림에 표시한 1번 인덱스에 map[0][:3] 이 삽입되고, 2번 인덱스에 map[1][:3]이 삽입, 3번 인덱스에는 map[2][:3] 이 삽입된다. 
이러한 방식으로 n=3인 배열이 n=9인 배열에 삽입된다.

이 코드를 이해하여 내것으로 만들기를 권장한다.

해당 글에 대한 오류는에 대한 지적은 언제나 환영입니다!😀