[Algorithm] 1일1솔 - 백준2447 별찍기-10 (python3)

문제링크

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

재귀함수로 푸는 문제이다. 규칙파악이 포인트이고, 그 이후에는 재귀로 풀면 된다.

 

규칙파악

일정하게 가운데가 뚫린 정사각형 패턴이 반복되고 있다.

예를 들어, 3(=3^1)일 때는 가운데에 공백이 있고 1(=3^0)개 씩의 별이 찍히고 있다.

따라서 패턴은 다음과 같다.

3^i일 때 가운데를 공백으로 하고, 3^(i-1) 개 씩의 별 찍는다.

또한, 정사각형의 가운데는 행과 열이 같을 때이므로 여기에 주목해서 코드를 짜면 된다.

 

재귀함수

그 다음으로 재귀함수를 활용하기 전에 일단 재귀함수의 개념부터 이해해보자.

재귀함수에서 알아두어야 할 자료구조는 스택(stack)이다.

stack의 특성상 재귀함수는 나중에 들어온 값이 제일 먼저 나가게 되는 후입선출(LIFO) 구조인데, 여기서도 제일 마지막에 호출한 함수를 제일 먼저 호출하는 과정을 거친다.

이해를 돕기 위해 간단히 1부터 n까지를 차례로 출력하는 문제를 봐보자.

def bottom_up(n):
    if n == 0:
        return
    bottom_up(n-1)
    print(n)

n = int(input())
bottom_up(n)

위 문제의 전체적인 흐름은 다음과 같다.

입력값에 5가 들어오게 되면 5는 0과 같지 않으므로 bottom_up(4)를 호출하게 된다.

bottom_up(4)는 0과 같지 않으므로 bottom_up(3)을 호출하게 되고 마지막으로 n이 0일 때는 return을 하게 된다.

return을 할 때는 스택에 호출되었던 함수들을 밑에서부터 다시 찾아간다.

bottom_up(0)을 호출한 n=1은 print(n)을 하게 되고 또 다시 올라가게 되는 식이다.

결과적으로 print는 1에서부터 n까지 출력하게 된다.

 

이러한 재귀의 특성을 이해하고 해당 문제도 응용하여 풀이하면 된다.

 

 

문제풀이

이 코드도 통과는 했으나, 시간이 다소 걸리며 채점되었다. 마지막에 별찍기를 할 때 arr[i][j] == 1 로 한 것이 arr 배열에서 i,j 에 해당하는 요소를 찾아가면서 시간이 걸리게 된 것 같았다. 

n = int(input())
arr = [[0 for _ in range(n)] for _ in range(n)]

def pattern(n):
    # n = 3^1일 때까지 재귀돌리고 배열 리턴시키기
    if n == 3:
        arr[0][:] = arr[2][:] = [1]*3
        arr[1][:] = [1,0,1]
        return

    div3 = n // 3
    pattern(div3)  # n을 3으로 나눈 값으로 재귀돌리기
    for i in range(3):
        for j in range(3):
            if i == 1 and j == 1:  # 가운데는 비우기 위해 패스
                continue
            else:
                for k in range(div3):
                    arr[div3*i+k][div3*j:div3*(j+1)] = arr[k][:div3] # 패턴 복붙


pattern(n)  # 재귀함수 초기값 n 넣고 돌리기
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            print('*',end='')
        else:
            print(' ',end='')
    print()

아래 코드는 위 코드를 수정해서 다시 채점해 본 코드이다. arr에서 요소를 찾지 않고 바로 i, j를 직접적으로 찾았기에 시간이 좀 더 단축되었다.

n = int(input())
arr = [[0 for _ in range(n)] for _ in range(n)]

def pattern(n):
    # n = 3^1일 때까지 재귀돌리고 배열 리턴시키기
    if n == 3:
        arr[0][:] = arr[2][:] = [1]*3
        arr[1][:] = [1,0,1]
        return

    div3 = n // 3
    pattern(div3)  # n을 3으로 나눈 값으로 재귀돌리기
    for i in range(3):
        for j in range(3):
            if i == 1 and j == 1:  # 가운데는 비우기 위해 패스
                continue
            else:
                for k in range(div3):
                   # print('arr[k]:',arr[k])
                    arr[div3*i+k][div3*j:div3*(j+1)] = arr[k][:div3]  # 패턴 복붙

pattern(n)  # 재귀함수 초기값 n 넣고 돌리기

# i,j를 range로 구하고 arr[i][j]로 탐색했던 부분의 시간 단축 위해 별찍기 부분을 수정
for i in arr:
    for j in i:
        if j:
            print('*',end='')
        else:
            print(' ',end='')
    print()