[Python] 백준 2447번 별 찍기-10 자세한 설명(재귀)

문제

풀이

재미있는 문제이기도 하고 내가 어떻게 생각했는지, 생각한 과정이 어떻게 되는 지 공유하고자 한다.

개인적인 생각이라, 더 좋은 방법이 있을 수 있다.

먼저 별을 찍을 2차원 리스트를 하나 만든다. 이 2차원 리스트는 공백(space)을 기본으로 갖는다.

n = int(input())

arr = [[' ' for _ in range(n)]for _ in range(n)]

그 다음 비슷한 패턴이 반복 된다는 것을 알 수 있다. 패턴은 밑의 그림과 같은데

일단 먼저 재귀로 아무 생각 없이 함수를 쓴다.

def star():

   

    star() #1

    star() #2

    star() #3

   

    star() #4

    star() #5

   

    star() #6

    star() #7

    star() #8

그 다음 각 칸의 간격을 생각해 본다. 간격은 항상 3의 제곱이다. 이 간격을 gap이라는 변수로 치환해 보자. 그러면 위의 패턴에서 왼쪽 위 칸의 좌표를 x,y로 생각한다면 모든 칸의 좌표는 밑의 그림처럼 된다.

위의 변경 사항을 재귀에 적용해 보자.

def star(x,y,gap):

   

    star(x, y, gap) #1

    star(x+gap, y, gap) #2

    star(x+gap*2, y, gap) #3

    star(x, y+gap, gap) #4

    star(x+gap*2, y+gap, gap) #5

    star(x, y+gap*2, gap) #6

    star(x+gap, y+gap*2, gap) #7

    star(x+gap*2, y+gap*2, gap) #8

이제 위 그림의 한 칸은 아홉 개로 분할 되어 계속 같은 패턴을 찍을 것이다.gap을 3개로 분할 시키면 아홉 개로 분할 된 각 칸의 간격이 된다. 

def star(x,y,gap):

    gap//=3

    star(x, y, gap) #1

    star(x+gap, y, gap) #2

    star(x+gap*2, y, gap) #3

    star(x, y+gap, gap) #4

    star(x+gap*2, y+gap, gap) #5

    star(x, y+gap*2, gap) #6

    star(x+gap, y+gap*2, gap) #7

    star(x+gap*2, y+gap*2, gap) #8

별을 찍을 2차원 arr를 넣어 주자.

def star(arr, x, y, gap):

   

    gap //= 3

    star(arr, x, y, gap)

    star(arr, x+gap, y, gap)

    star(arr, x+gap*2, y, gap)

    star(arr, x, y+gap, gap)

    star(arr, x+gap*2, y+gap, gap)

    star(arr, x, y+gap*2, gap)

    star(arr, x+gap, y+gap*2, gap)

    star(arr, x+gap*2, y+gap*2, gap)

마지막으로 gap의 값이 0, 즉 더 이상 이 칸을 분할할 수 없다면(arr[x][y]인 한 요소만을 가리킨다면,) x,y 자리에 별을 찍게 만든다.

def star(arr, x, y, gap):

    if gap == 0:

        arr[y][x] = '*'

        return

    gap //= 3

    star(arr, x, y, gap)

    star(arr, x+gap, y, gap)

    star(arr, x+gap*2, y, gap)

    star(arr, x, y+gap, gap)

    star(arr, x+gap*2, y+gap, gap)

    star(arr, x, y+gap*2, gap)

    star(arr, x+gap, y+gap*2, gap)

    star(arr, x+gap*2, y+gap*2, gap)

이러면 별을 찍는 함수가 완성된다.

완성된 코드

def star(arr, x, y, gap):

    if gap == 0:

        arr[y][x] = '*'

        return

    gap //= 3

    star(arr, x, y, gap)

    star(arr, x+gap, y, gap)

    star(arr, x+gap*2, y, gap)

    star(arr, x, y+gap, gap)

    star(arr, x+gap*2, y+gap, gap)

    star(arr, x, y+gap*2, gap)

    star(arr, x+gap, y+gap*2, gap)

    star(arr, x+gap*2, y+gap*2, gap)

n = int(input())

arr = [[' ' for _ in range(n)]for _ in range(n)]

star(arr, 0, 0, n)

for i in arr:

    print(''.join(i))

출력해 본 결과이다.