[백준 2447] 별 찍기 - 10

별 찍기 - 10 (2447)

문제 출처 : https://www.acmicpc.net/problem/2447

 

반복문에 대해 처음 배웠을 때 시작하는 것이 별 찍기 입니다. 아직 별 찍기가 무엇인지 잘 모른다면 아래 링크를 통해 별 찍기가 무엇인지 알아보기 바랍니다.

https://wikidocs.net/192041

03. 별 찍기

 

백준에는 다양한 별 찍기 문제가 있으니 아직 별 찍기 이전 문제들을 풀어보지 못했다면 풀어보시기 바랍니다. 아래 링크를 들어가면 여러 가지 형태의 별 찍기 문제를 볼 수 있습니다.

https://www.acmicpc.net/workbook/view/20

 

여러가지 별 찍기 문제 중 재귀를 통해 문제를 해결해야 하는 별 찍기 10을 확인해 보겠습니다.

어려워 보이지만 쉽게 규칙을 찾을 수 있습니다. 바로 아래와 같은 형태로 계속 만들고 있다는 것입니다.

크게 보면 이런 모양이고 각각의 패턴 하나 하나가 또 네모 모양으로 되어 있습니다. 이것이 누적되어 예제와 같은 모양이 되는 것입니다. 우리는 패턴 하나하나를 재귀적으로 자신과 같은 모양으로 만들어 줍니다.

코드 작성

코드를 작성해 나가며 알아보겠습니다.

입력 받기

N = int(input())

별을 찍을 전체 크기 N을 입력 받습니다. N은 3의 거듭제곱이기 때문에 3의 배수가 아닌 형태를 고려할 필요가 없습니다.

출력하기

dp = [[' '] * (N) for _ in range(N)]
for i in range(N):
    print(*dp[i], sep='')

별을 하나하나 찍어주기 힘들기 때문에 리스트로 만들어 출력하기 쉽게 만들어 주었습니다. 자세히 보면 print 문에 * 표시도 있고, sep라는것도 보입니다. 이것에 대해서 잘 모른다면 아래 링크를 확인 바랍니다.

https://wikidocs.net/192130#sep

04. 다양한 print 문 사용법

 

위와 같은 설명이 있기는 하지만 그래도 잘 모르겠다면 아래처럼 코드를 바꿔 보겠습니다.

N = 9
dp = [['*'] * (N) for _ in range(N)]
for i in range(N):
    print(dp[i])

보이지 않는 빈칸 대신 “*” 으로 바꿔 어떻게 표시되는지 확인할 수 있습니다.

보는 것과 같이 “*” 이 9개 씩 9줄이 되어 있는것을 알 수 있습니다.

이제 print문을 아래와 같이 바꿔줍니다.

    print(*dp[i])

*을 리스트 앞에 붙여 Unpacking 된 리스트가 출력 됩니다.

이제 여기에 sep를 통해 원소 하나하나마다 있는 빈 칸을 제거 합니다.

    print(*dp[i], sep="")

그럼 아래와 같이 별표들이 빈 칸 없이 붙어있는 것을 볼 수 있습니다.

재귀 함수 만들기 1

이제 어떻게 출력하는지 알았으니 별표를 찍어줄 함수를 만들어 보겠습니다.

def solve(n, y, x):
    pass
		
solve(N, 0, 0)

제가 정의한 함수는 3개의 인자를 받습니다. 첫 번째 인자 n은 별 찍기를 할 전체 크기 입니다. 다음으로 y좌표와 x좌표를 입력 받습니다. 여기서 solve(N, 0, 0)은 N의 크기로 0, 0 좌표에서 시작하는 별 찍기를 해달라는 뜻입니다.

재귀 함수 만들기 2

이제 가로, 세로 3칸씩 별을 찍어주는 로직을 만들어 줍니다.

def solve(n, y, x):
    m = n // 3
    for i in range(3):
        for j in range(3):
            if i == j == 1:
                continue
            solve(m, y + i * m, x + j * m)

총 9번을 반복하는데 가운데는 찍지 않기 때문에 i, j 값 모두 1인 경우 다음으로 넘어갑니다. 크기는 처음 크기에서 1 / 3으로 줄어 듭니다. m의 값이 3분의 1로 줄어든 크기를 저장합니다. 크기는 3분의 1로 줄었고 각각의 x, y 좌표값이 변경 됩니다.

재귀 함수 만들기 3

마지막으로 종료 조건을 추가해 줍니다.

def solve(n, y, x):
    if n == 1:
        dp[y][x] = '*'
        return

n의 크기가 1이 되었을 때 더 이상 재귀 함수를 쓰는 것이 아니라 해당 위치에 “*”을 찍어 줍니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())
dp = [[' '] * (N) for _ in range(N)]

def solve(n, y, x):
    if n == 1:
        dp[y][x] = '*'
        return
    
    m = n // 3
    for i in range(3):
        for j in range(3):
            if i == j == 1:
                continue
            solve(m, y + i * m, x + j * m)

solve(N, 0, 0)
for i in range(N):
    print(*dp[i], sep='')