백준 2447번 풀이

문제

시어핀스키 사각형을 별찍기로 구현하는 문제. 망델브로 아닌게 어디임

참고문헌

https://cotak.tistory.com/38

일단 풀이가 두 개 있는데 2번이 쉽다고 함… 본인은 1번이 와닿아서 그거 참고함.

풀이

일단 풀기 전에 시어핀스키 사각형에 대해 보고 가자.

이놈이 시어핀스키 카펫(시어핀스키 사각형)이다.

시어핀스키 카펫은 프랙탈의 일종인데, 프랙탈은 그냥 똑같은 모양이 계속 반복되는 모양이다. 시어핀스키 카펫은 사각형을 9등분 한 다음 가운데를 지우고 그 사각형을 또 9등분해서 가운데 날리고 이런 식으로 반복되는 프랙탈의 일종. 이게 3차원이 되면 맹거 스펀지가 된다.

참고로 자매품으로 시어핀스키 삼각형도 있다. 이걸 코딩하라고 하면 개쌉고인물이 아닌 이상 힘들다.

일단 2번 풀이는 공간을 가로로 3등분하고 재귀함수를 통해 반복하는 형식이고(그래서 더 쉽다) 1번 풀이는 공간을 9등분 한 다음 5번째 공간을 공백으로 두는 방식이다. 그래서 배열이라는 개념이 나오는데… 어? 넘파이 있어야돼요? 아뇨 그러면 백준에서 빠꾸먹습니다…

arr1 = [['*' for i in range(3)] for j in range(3)]
for i in range(3):
  for j in range(3):
    print(arr1[i][j],end="")
  print()

넘파이 없어도 배열 만들 수는 있다. 저기서 3을 n으로 바꾸면 n*n으로 배열을 만드는 것도 가능하다. 물론 2차원 좌표 지정이나 슬라이싱도 넘파이랑 비슷하게 할 수 있다. (arr[i][j] 이런 식으로)

import sys 
sys.setrecursionlimit(10**6) 

def star(row):
    div3 = row // 3
    if row == 3:
        arr[1] = ['*', ' ', '*'] 
        arr[0][:3] = arr[2][:3] = ['*'] * 3
        return

    star(div3)
    
    for i in range(0, row, div3): 
        for j in range(0, row, div3): 
            if i != div3 or j != div3: 
                for k in range(div3): 
                    arr[i+k][j:j+div3] = arr[k][:div3] 
                    
n = int(input())
arr = [[' ' for _ in range(n)] for _ in range(n)]
star(n)

for i in range(n): 
    for j in range(n): 
        print(arr[i][j], end='') 
    print()

row, 그러니까 입력한 값이 3일 때는 별별별 별 별 별별별이 출력된다. 엥? 근데 저 for문에 range는 뭔가요? 자, 입력을 9로 예시를 들면 0, 9, 3이 된다. (div3 = 입력값을 3으로 나눈 몫이니까 3) 그래서 0, 3, 6이 나오게 된다. 저기서 i가 3이 아니거나 j가 3이 아니면 들어가게 되는 for문의 범위가 3이 되어서 arr[i+k][j:j+3] = arr[k][:3]이 된다는 얘기. :3은 슬라이싱인데 0부터 할거라 0 생략한거라고 보면 된다. 그럼 여기서 i+k는 어떻게 될까?

위에서 9를 예시로 들었으니 9로 갑시다. 그러면

그러면 저 배열에서 호출하게 되는 위치가 잡힐것이다. 배열의 [k][:div3]은 [0][:3], [1][:3], [2][:3]이다.

어? 그럼 둘다 3이면? 위에서 i랑 j가 둘 다 0, 3, 6이라고 했는데 저기서 3,3이면 가운데라 뭘 채울 게 없다. (뇌피셜 주의)

*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
* *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * *
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*********         ******************         ******************         *********
* ** ** *         * ** ** ** ** ** *         * ** ** ** ** ** *         * ** ** *
*********         ******************         ******************         *********
***   ***         ***   ******   ***         ***   ******   ***         ***   ***
* *   * *         * *   * ** *   * *         * *   * ** *   * *         * *   * *
***   ***         ***   ******   ***         ***   ******   ***         ***   ***
*********         ******************         ******************         *********
* ** ** *         * ** ** ** ** ** *         * ** ** ** ** ** *         * ** ** *
*********         ******************         ******************         *********
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
* *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * *
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
***************************                           ***************************
* ** ** ** ** ** ** ** ** *                           * ** ** ** ** ** ** ** ** *
***************************                           ***************************
***   ******   ******   ***                           ***   ******   ******   ***
* *   * ** *   * ** *   * *                           * *   * ** *   * ** *   * *
***   ******   ******   ***                           ***   ******   ******   ***
***************************                           ***************************
* ** ** ** ** ** ** ** ** *                           * ** ** ** ** ** ** ** ** *
***************************                           ***************************
*********         *********                           *********         *********
* ** ** *         * ** ** *                           * ** ** *         * ** ** *
*********         *********                           *********         *********
***   ***         ***   ***                           ***   ***         ***   ***
* *   * *         * *   * *                           * *   * *         * *   * *
***   ***         ***   ***                           ***   ***         ***   ***
*********         *********                           *********         *********
* ** ** *         * ** ** *                           * ** ** *         * ** ** *
*********         *********                           *********         *********
***************************                           ***************************
* ** ** ** ** ** ** ** ** *                           * ** ** ** ** ** ** ** ** *
***************************                           ***************************
***   ******   ******   ***                           ***   ******   ******   ***
* *   * ** *   * ** *   * *                           * *   * ** *   * ** *   * *
***   ******   ******   ***                           ***   ******   ******   ***
***************************                           ***************************
* ** ** ** ** ** ** ** ** *                           * ** ** ** ** ** ** ** ** *
***************************                           ***************************
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
* *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * *
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*********         ******************         ******************         *********
* ** ** *         * ** ** ** ** ** *         * ** ** ** ** ** *         * ** ** *
*********         ******************         ******************         *********
***   ***         ***   ******   ***         ***   ******   ***         ***   ***
* *   * *         * *   * ** *   * *         * *   * ** *   * *         * *   * *
***   ***         ***   ******   ***         ***   ******   ***         ***   ***
*********         ******************         ******************         *********
* ** ** *         * ** ** ** ** ** *         * ** ** ** ** ** *         * ** ** *
*********         ******************         ******************         *********
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
* *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * ** *   * *
***   ******   ******   ******   ******   ******   ******   ******   ******   ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************

이게 해당 코드로 81에 대해 돌린 결과이다.

*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

9는 이런 식. 얘는 입력값에 대한 처리를 하고 입력값을 3으로 나눈걸 호출 호출 호출 하다가 최종 값이 3이 되면 별별별 별 별 별별별 부른다.

준비물: 얼굴 아니