[백준] 10993 - 별 찍기 - 18

1. 문제

10993번 - 별 찍기 - 18

2. 개요

재귀를 활용한 별 찍기 문제.

3. 코드 및 추가내용

import sys

N = int(sys.stdin.readline())
k = -1

for i in range(1,N+1):
    k += 2**i

board = [[" "] * k for j in range((2**N)-1)]

start = -1 if N % 2 == 0 else 0

def drawTree(idx, now):
    l, r = len(board[now]) // 2, len(board[now]) // 2
    board[now][l] = '*'
    go = -1 if idx % 2 == 0 else 1

    while l != 0 and board[now][l-1] != '*':
        now = now + go
        l, r = l-1, r+1
        board[now][l], board[now][r] = '*', '*'

    board[now][l:r] = ['*'] * (r-l)
    
    if idx == 1:
        for z in board:
            print(''.join(z).rstrip())
    elif idx % 2 == 0:
        drawTree(idx - 1, now + 1)
    else:
        drawTree(idx - 1, now - 1)

drawTree(N, start)

일단 패턴을 찾는다.

트리의 최종 너비는 $(\displaystyle\sum_{i=1}^{N}{2^i}) - 1$ 이고, 트리의 최종 높이는 $2^N-1$ 이므로,

각각을 열, 행으로 하는 리스트를 만들어준다.

또한 N이 짝수일 땐 역방향 - 정방향 - 역방향 … , N이 홀수일 땐 정방향 - 역방향 - 정방향 … 이고,

정점 한가운데의 점을 시작으로 1칸씩 점점 넓어져가다가 최하단에서는 모든 칸을 채운다.

모든 트리는 정점에서부터 그려나가기로 한다.

N이 짝수라면 가장 아래부터, 홀수라면 가장 위부터 시작할테니 start변수를 이에 맞게 설정해둔다.

정점 행부터 최하단까지 한칸씩 늘려나가야 하기 때문에 l,r을 설정하고 정점의 별도 찍는다.

한 칸씩 내려가며 l,r 을 각각 한 칸씩 이동시킨 후 별을 찍는다. 이때 l또는 r이 최대 너비에 도달하거나, 이미 별이 찍힌 곳에 위치했다면 그곳이 별 트리의 최하단이라는 의미이므로 l부터 r까지 모두 별로 도배해준다.

한 트리를 완성했다면 이제 방향을 뒤집어 새 트리를 만들어준다.

방금까지 정방향 트리를 그렸다면 최하단의 바로 윗 칸이 다음 트리의 정점일 것이고, 역방향 트리였다면 최하단의 바로 아랫 칸이 다음 트리의 정점일 것이기에 1줄어든 인덱스와 다음 트리의 정점을 인자로 넘겨 재귀를 돌린다.

인덱스가 1이라면 별을 마저 찍고 완성된 트리를 프린트한다.

import sys

N = int(sys.stdin.readline())
k = -1

for i in range(1,N+1):
    k += 2**i

board = [[" "] * k for j in range((2**N)-1)]

start = -1 if N % 2 == 0 else 0

now = start
while N > 0:
    l, r = len(board[now]) // 2, len(board[now]) // 2
    board[now][l] = '*'
    go = -1 if N % 2 == 0 else 1

    while l != 0 and board[now][l-1] != '*':
        now = now + go
        l, r = l-1, r+1
        board[now][l], board[now][r] = '*', '*'

    board[now][l:r] = ['*'] * (r-l)
    
    N -= 1
    now = now - 1 if N % 2 == 0 else now + 1

for z in board:
    print(''.join(z).rstrip())

사실 굳이 재귀 안해도 반복문으로도 풀린다. 속도도 이게 더 빠르더라.