[백준] 2448번 별 찍기 - 11 (Python)

정답 코드 및 풀이는 맨 아래에 있습니다.

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

• 역시 골드 넘어가는 재귀문제는 난이도가 살짝 있다. 구상과 구현 모두 쉽지 않았다.

---

< 별 찍기 - 11 > 

[문제]

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

[입력]

첫째 줄에 N이 주어진다. N은 항상 3×2^k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

[출력]

첫째 줄부터 N번째 줄까지 별을 출력한다.

예제 입력	예제 출력
24

---

아이디어

한 삼각형 당 내부 삼각형이 네 개가 있다. 가운데 삼각형은 싹 비우고, 나머지 세 삼각형은 다시 재귀함수를 호출해 가운데 삼각형을 비워준다. 세 삼각형 각각에 대한 나머지 세 삼각형에서 또 재귀함수를 호출하고 ... 이를 반복하여 전체 삼각형을 만들 수 있다고 생각하였다.

풀이 및 코드

def printBoard(n):
    for row in range(n):
        for col in range(2 * n - 1):
            if board[row][col]:
                print('*', end = "")
            else :
                print(' ', end = "")
        print()

def initTriangle(n):
    # 0번째 줄 부터 n - 1번째 줄 까지 반복
    for row in range(n):
        # 각 줄 마다 n - 1행이 중앙이고, 각 row의 중앙부터 양 쪽으로 row개만큼 1로 바꾼다.
        # 예를 들어 세 번째 줄이면 board[3][3] = 1, board[3][2], board[3][4] = 1, board[3][1], board[3][5] = 1이다.
        for col in range(row + 1):
            board[row][n - 1 - col] = 1
            board[row][n - 1 + col] = 1

# 각 삼각형의 가운데 삼각형을 빈 칸으로 바꾸는 함수.
# 꼭짓점의 행, 열, 삼각형의 높이가 인자로 들어온다.
def recFillBlank(top_row, top_col, height):
    # 높이가 3인 삼각형일 때 재귀 종료
    if height == 3:
        # 가운데 한 칸만 0으로 바꿔줌
        board[top_row + 1][top_col] = 0
        return
    lowest_line = top_row + height - 1
    # 가장 아래 줄부터 윗 방향으로 높이 // 2만큼 실행함.
    for row in range(height // 2):
        # initTriangle함수와 같은 방식으로 0으로 바꿔줌.
        for col in range(row + 1):
            board[lowest_line - row][top_col - col] = 0
            board[lowest_line - row][top_col + col] = 0
    # 나머지 세 삼각형에 대해 다시 빈 칸을 0으로 바꿔주는 함수 호출
    recFillBlank(top_row, top_col, height // 2)
    recFillBlank(top_row + height // 2, top_col - height // 2 , height // 2)
    recFillBlank(top_row + height // 2, top_col + height // 2 , height // 2)

n = int(input())
board = [[0 for _ in range(2 * n - 1)] for _ in range(n)]
initTriangle(n)
recFillBlank(0, n - 1, n)
printBoard(n)

삼각형의 내부를 빈 칸으로 바꿔주는 것에서 조금 어려움이 있었다. 행과 열의 인덱스를 잘 맞춰주어야 했다. 삼각형의 내부를 빈칸으로 바꿔주는 경우, 가운데 꼭짓점의 열을 기준으로 좌 우로 대칭되게 빈칸으로 바꿔주면 된다. 즉, 삼각형의 맨 아랫줄의 가운데 부분을 0으로 바꿔주고, 그 윗 줄은 가운데와 양 옆 한 칸씩을 0으로, 그 윗 줄은 양 옆 한 칸씩 더 0으로 바꿔주고 ... 이를 반복하여 가운데 줄까지 0으로 바꿔주면 중앙 삼각형이 모두 0으로 바뀐다.

다른 사람들은 python3로도 정답처리 받았다.

나는 이 알고리즘이 정석적이고 충분히 빠를 것이라고 생각하였다. 하지만 python3로는 시간초과가 났고, pypy로만 통과하였다. 하지만 다른 사람들은 python3로도 매우 빠른 속도로 풀어냈다. 이 코드들을 보았다.

다른 코드

def star(height):
    # 재귀 종료 조건
    if height == 3:
        return ["  *  "," * * ","*****"]
    # 재귀 함수를 호출해 이전 단계 별 박스를 저장한다.
    prev_level_stars = star(height // 2)
    # 현재 단계 삼각형 리스트에 이전 별 박스를 여러 개 붙여 저장한다.
    now_level_stars = []
    for each_line in prev_level_stars:
        # 먼저, 이전 별 박스의 양 옆에 n의 절반만큼의 공백을 붙인다.
        now_level_stars.append(" " * (height // 2)  + each_line + " " * (height // 2))
    for each_line in prev_level_stars:
        # 그 다음에 공백으로 구분하여 두 개의 별 박스를 이어붙인다.
        now_level_stars.append(each_line + " " + each_line )
    return now_level_stars
    
n = int(input())
print("\n".join(star(n)))

다른 코드를 보는데 어려움이 아주 많았다. 변수명은 알아보기 쉽게 작성하는 사람이 거의 없었고, 나와 다르게 연산자마다 띄어쓰기를 하지 않은 사람이 많았다.(이건 취향차이) 가독성이 좋은 코드가 별로 없어서 해석하기 힘들었다. 함수 중간중간에 각 변수를 프린트하는 코드를 넣어 셀프 디버깅하며 어찌저찌 이해하였고, 다른 코드를 참고하여 내 방식대로 작성하여 보았다.

아래 알고리즘은 첫 번째 삼각형을 배열에 저장해두고, 다음 단계 삼각형이면 그 삼각형 세 개를 붙이고, 또 그다음 단계 삼각형이면 이전 단계 삼각형 세 개를 붙이는 방식이었다. 이렇게 하니 내 코드보다 훨씬 빠른 함수가 되었다. 내 코드는 기본적으로 먼저 삼각형을 꽉 채워놓은 다음에 재귀적으로 한 개씩 빈칸은 0으로 수정하는 방식이다. 하지만 아래 코드는 세 줄이 단위가 되어 작동한다. 첫 줄은 나처럼 하나하나 인덱스로 접근하여 수정하는 것이 아니고 문자열 이어 붙이기여서 구현에도 어려움이 없고, 각 줄을 한 번에 실행하기 때문에 내 코드보다 훨씬 적은 시간으로 작동한 것 같다.(문자열 슬라이싱이라 시간이 조금 더 걸릴 순 있지만, 한 번만 실행하면 되기 때문이다. 내 코드는 한 줄에 있는 알맞은 인덱스에 접근해 1을 0으로 수정해주는 방식이다.)

후기

내 아이디어대로 구현하면서 굉장히 많은 즐거움과 뿌듯함을 느꼈다. 그리고 나보다 더 좋은 코드를 보고 학습하는 과정을 통해 성장을 느꼈다. 역시 재귀는 넓게 볼 수 있는 능력이 가장 중요한 것 같다. 다소 어렵긴 하지만 나한테는 제일 재미있는 알고리즘인 것 같다. 몇 문제 더 풀고 마무리해야겠다!