[Python/파이썬] 백준 1030번 프렉탈 평면

1030번: 프렉탈 평면

 

문제

프렉탈 평면은 다음과 같이 커진다. 시간 0에서 프렉탈은 흰색 정사각형 하나이다. 단위 시간(1)이 진행될 때마다 N×N개의 크기가 동일한 단위 정사각형으로 나누어진다. 만약 나누어진 정사각형이 흰색이라면 가운데 K×K 정사각형이 검정색으로 채워진다. N과 K는 둘 다 홀수이거나, 둘 다 짝수이다.

예를 들어, N=3, K=1이라면, 시간 1에 3×3 정사각형이 된다. 가운데 정사각형은 검정색이고, 나머지는 흰색이 된다. 시간 2때 9×9 정사각형이 되고, 17개는 검정이고, 나머지는 흰색이다.

s, N, K, R1, R2, C1, C2가 주어질 때, 시간 s일 때, R1행 C1열부터 R2행 C2열까지의 모습을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 첫째 줄에 R1행의 모습을 출력하고 이런 식으로 총 R2-R1+1개의 줄에 출력하면 된다. 각 행의 모습을 출력할 때, C1열부터 C2열까지 차례대로 흰색이면 숫자 '0' 검정이면 숫자 '1'을 출력한다. 숫자 사이에 공백을 넣으면 안 된다.

코드

s, n, k, r1, r2, c1, c2 = map(int, input().split())

if s == 0:
    print(0)
    exit()

# (x, y)가 검은색인지 흰색인지 판단
def fractal(length, x, y):
    if length == 1:
        return 0
    c = length//n   # n개로 나눠졌을때 길이
    # 검은 부분에 해당되면 1 리턴
    if (c * (n-k)//2) <= x < (c * (n+k)//2) and (c * (n-k)//2) <= y < (c * (n+k)//2):
        return 1
    return fractal(c, x%c, y%c)

for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        print(fractal(n**s, i, j), end='')
    print()

 

출력하려는 범위의 각 칸에 대하여 그 칸이 검은색인지 흰색인지 판단한다.

판단하기 위한 함수인 fractal()은 각 단계의 나눠진 칸의 길이와 판단하려는 칸의 좌표를 매개변수로 받는다. 해당 좌표가 검은색으로 칠해지려는 칸이라면 1을 리턴하고 그렇지 않고 길이가 1에 도달한다면 흰색칸이므로 0을 리턴한다.

 

처음 봤을 때는 검은 부분에 해당되는지 판단하는 조건문이 헷갈렸는데 그림으로 그려서 이해해보면 다음과 같다.

 

문제를 보자마자 분할정복, 재귀를 이용하여 풀어야겠다는 생각은 들었는데 구현이 어려웠던 문제였다. 결국 이리저리 해보다가 너무 오래걸려서 구글링해서 여러 블로그를 참조해서 풀었다.