백준 2447번 - 별 찍기 - 10

기본적인 패턴이 반복이 되는 별 찍기 문제이다. N = 3일때의 기본 형태가 N이 커짐에 따라 반복이 되는 형태이다.

기본 형태는 9개의 별에서 가운데 하나가 빠진 8개로 이루어져있다. NXN크기의 2차원 배열을 0으로 초기화한다. 0은 별이 찍히지 않음을 의미한다. 문양을 만들기 위해서는 기본 형태를 계속해서 찍어주면 되는데 그러기 위해서는 좌표가 필요했다. star함수에는 N과 시작 좌표인 0,0을 전달해 준다. 그리고 N을 3으로 나누어 주면서 다시 호출해주면서 별을 찍어주면 되겠다. N이 계속 호출되며 결국 1이 될 때 좌표에 별을 찍어주면 된다. 그렇다면 어떻게 좌표를 찍어야 할까?

생각보다 간단하다. 좌표는 N이 9라고 가정하면, (0,0) ~ (2,2), (0,3) ~ (2,5), (0,6) ~ (2,8) 식으로 3의 배수만큼 어떤 수에 더하고 0,1,2를 반복해서 더해주는 식으로 진행이 된다. star에서 받은 좌표에 3 X 3만큼 이중 for문을 사용해서 더해주면 된다.  

##함수 선언 부분
def star(num, a, b):
   if num == 1:
       is_star[a][b] = 1 #좌표에 1을 넣어준다
   else:
       for a1 in range(3):
           for b1 in range(3):
               if a1 != 1 or b1 != 1: #가운데는 비워야한다
                   star(num//3, a + a1 * num//3, b + b1 * num//3)
                   #들어온 좌표 + 0부터 2에 num//3을 곱한 값을 더해주어 좌표를 구한다


##변수 선언 부분
N = 0
max_num = 0
##메인 함수 부분
if __name__ == "__main__":
    N = int(input())
    is_star = [[0 for col in range(N) ] for row in range(N)]
    max_num = N
    star(N, 0, 0)
    for i in range(0, N):
        for j in range(0, N):
            if is_star[i][j]:
                print("*",end="")
            else:
                print(" ",end="")
        print("")

1학년 때 질리도록 했던 별찍기라 쉽게 풀 수 있을거라고 생각했지만, 큰 오산이었다. 재귀를 이용해서 풀어야 된다는 것을 알았지만 어디부터 시작해야될 지 감도 못잡았다. 처음에 짰던 코드는 NXN 배열에 모두 1을 넣고 가운데 공간을 삭제해주는 식으로 코드를 짰지만 역시나 시간초과가 떴다. 이미 삭제된 곳을 다시 삭제하는 경우 때문에 발생한 것 같다.