BOJ 2447번 : 별 찍기 - 10

안녕하세요. 지난 포스팅의 BOJ 17478번 : 재귀함수가 뭔가요? 에서는 재귀함수를 이용해서 문자열을 출력하는 문제를 풀어보았습니다. 오늘은 다시 이전에 반복문 파트에서 보았던 별 찍기 문제의 심화버전을 풀어보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 재귀함수의 정의

 

제출 코드

N = int(input())

star = [[' '] * N for i in range(N)]
def stars(N, x, y) :
    if N == 3 :
        for i in range(3) :
            for j in range(3) :
                star[x + i][y + j] = '*'
        star[x + 1][y + 1] = ' '
    else :
        for i in range(3) :
            for j in range(3) :
                if i != 1 or j != 1 : 
                    stars(N // 3, x + (N // 3) * i, y + (N // 3) * j)
    
stars(N, 0, 0)
for r in star :
    print(''.join(r))

 

해설

기본적으로 별 찍기 문제는 패턴을 파악해야합니다. 그리고 이 문제는 재귀함수로 해결해야하기 때문에 무조건 종료조건이 명시되어있어야하죠. 이는 문제에서 답을 알려주고 있습니다. $N = 3$일 때 가장 작은 값으로 아래와 같이 구성되어 있습니다. 

 

***
* *
***

 

 

그렇다면 해당 종료조건을 먼저 써줘야겠네요. 제출 코드의 함수에서 아래 부분이 해당 재귀함수의 종료조건을 의미합니다. 

 

if N == 3 :
    for i in range(3) :
        for j in range(3) :
            star[x + i][y + j] = '*'
    star[x + 1][y + 1] = ' '

 

$N = 3$이면 이제 처음에 봤던 문자열을 출력하기 위해서 미리 선언해놓은 star 이중 리스트 변수에 현재 좌표 $(x, y)$를 기준으로 가운데를 제외하고는 전부 별로 채워주게 됩니다. 이제 종료조건이 아닌 경우에는 또 함수를 호출해서 재귀적으로 해결해야겠죠? 

 

else :
    for i in range(3) :
        for j in range(3) :
            if i != 1 or j != 1 : 
                stars(N // 3, x + (N // 3) * i, y + (N // 3) * j)

 

위 코드는 현재 좌표 $(x, y)$와 $N$이 주어졌을 때 바로 아래 단계($N = 9$이면 $N = 3$)에 대한 별을 그리기 시작합니다. 예시로 $N = 9$, 그리고 현재 좌표는 $(0, 0)$라고 했을 때 $(0, 0), (0, 3), (0, 6), (3, 0), (3, 3), (3, 6), (6, 0), (6, 3), (6, 6)$를 새로운 시작 좌표라고 보고 별을 찍는 것이죠. 

 

참고자료 및 그림출처

백준 코딩 문제