(Python/파이썬) - 백준(BOJ) 1030번 : 프랙탈 평면

https://www.acmicpc.net/problem/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열까지의 모습을 출력하는 프로그램을 작성하시오.

 

예제 입력 : 

3 3 1 4 11 5 10

예제 출력

101001
100000
000000
001001
000000
000011
001011
000011

예제 설명

 

---

• 풀이 :

재귀를 사용한 분할정복을 사용하는 문제였습니다.

 

우선, N ^S 의 배열을 만들어서 실제로 값을 채우는 방법을 고려하였지만 메모리 낭비가 심하다고 판단하여 주어진 좌표인

R1, R2, C1, C2의 범위에 해당하는 좌표만 탐색하게 했습니다.

 

풀이 아이디어는 다음과 같습니다. 

 

1. 한 변의 길이 (정사각혐이므로 행과 열은 동일합니다.) 를 l로 미리 계산해둡니다. 이 값은 N ^ S 의 수식으로 계산할 수 있습니다.

 

2. R1,R2와 C1,C2 의 범위 안의 모든 좌표에 대해 해당 칸이 검정색 칸일지 흰색 칸일지 확인하는 함수를 호출합니다.

 

3. 출력 양식에 맞게 출력합니다.

 

아이디어는 간단하나 구현이 쉽지 않았습니다.

 

 

문제 해결 알고리즘의 구현입니다.

 

1. 입력을 받고 l 값을 미리 계산한다.

 

2. 이중 for문을 사용하여 R1~ R2, C1~C2의 모든 좌표에 대해 check_black 함수를 호출한다.

 

3. check_black 함수는 재귀함수이며 매개변수로 한 변의 길이와 현재 좌표를 받는다.

 

- 한 변의 길이가 1이라면 그 좌표값은 흰색이어야 하므로 0을 리턴한다. 

 

- 좌표값이 가운데의 K만큼의 범위 (검정색이 들어가야 할 범위) 안에 포함된다면 이 좌표값은 검정색이므로 0을 리턴한다.

 

- 한 변의 길이를 N 으로 나누어 재귀호출한다. (Top - Down 방식으로 진행)  이 때, board의 범위가 줄었으므로 현재 좌표인 x와 y도 해당 범위에 맞게 좌표를 변경하여 호출해야 한다. 

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

def check_black(l, point):
    x,y = point # 현재 탐색중인 좌표
    center = l//N # 검정색 칸의 범위
    if l == 1:
        return 0
    if center * (N-K)//2 <= x < center * (N+K)//2 and center * (N-K)//2 <= y < center * (N+K)//2:
        return 1
    x %= center
    y %= center
    return check_black(l//N, [x,y])
s,N,K,R1,R2,C1,C2 = map(int,input().split())
l = N**s # 한 변의 길이


for i in range(R1, R2+1):
    for j in range(C1, C2+1):
        print(check_black(l,[i,j]), end="")
    print()