[재귀 / 파이썬] 백준 1030번 : 프렉탈 평면*** / 골드 3

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

1030번: 프렉탈 평면

s, n, k, x1, x2, y1, y2 = map(int, input().split())

m = (n - k) // 2

def check(x, y, t):
    if t == 0:
        return 0

    nn = n**(t-1)
    
    nx = x // nn
    ny = y // nn
    if m<=nx<m+k and m<=ny<m+k:
        return 1
    else:
        return check(x % nn, y % nn, t-1)

for i in range(x1, x2+1):
    for j in range(y1, y2+1):
        print(check(i, j, s), end = '')
    print("")

문제가 굉장히 오래 걸렸다.

첫번째 풀이법으로 프랙탈 구조를 직접 전부 만든뒤 해당되는 범위를 출력하는 것이었다.

하지만 숫자가 꽤 커질수록 전체 프랙탈 구조의 행, 열 개수는 최대 64*(3**10)까지 커지기 때문에

이 방법은 사실상 불가능하다.

 

두번째 풀이법으로 해당되는 i, j 좌표의 색이 흰인지 검인지 직접 조사하는 것이다.

이렇게 되면 굳이 전체 프랙탈 구조를 알지 않아도 된다.

그럼 문제는 어떻게 특정 좌표의 흰/검을 구별하냐는 것이다.

 

나도 계산이 너무 헷갈려서 갈피를 못잡고 여러 시도를 하다가, 그래도 최선의 생각체계를 고안해냈다.

기본적인 구조는 재귀구조를 이용해가면서 구역의 중앙에 해당하는 지 체크하면 된다.

어차피 검은색은 최초에 중앙에 칠해지고, 시간이 지날수록 구역이 나뉘면 또 그 구역들의 중앙에 각각 칠해진다.

중앙 여부는 다음과 같이 구한다.

m = (n - k) // 2
if m<=nx<m+k and m<=ny<m+k

여기서 헷갈리고 중요한건 nx, ny를 구하는 것이다.

코드를 보면 nn = n**(t-1)을 구했는데 이게 무엇인지 아는 게 중요하다.

**nn은 해당 구역에서 다시 잘게 쪼개지는 자식 구역의 열 길이다. **

이 열 길이로 나눈 몫을 구해야 내 위치가 어느 자식 구역에 존재하는 지 알아낼 수 있기 때문이다.

x, y 가 실제 좌표라면 nx, ny는 자식 구역의 위치를 담고 있다.

이런 방식으로 중앙 여부를 체크하고

중앙이 아니라면 재귀를 통해 자식 구역을 다시 현재 구역으로 설정을 하고 깊이 파고 들어가야한다.

이때 파라미터는 코드에서 보면 다음과 같이 넘겨주었다.

return check(x % nn, y % nn, t-1)

x%nn, y%nn <= 이 부분도 처음 생각해낼 때는 매우 헷갈렸다.

x%nn, y%nn 을 넘겨주는 이유는 자식 구역 내에서의 위치를 알아내기 위해서다.

모듈러 연산의 결과는 어차피 0~nn내에서 돌기 때문에 쉽게 생각하면 bias를 조정해주는 느낌이다. 

t-1로 넘겨주는 이유는 자식 구역의 열 길이를 새로 구해준 것이다.

비슷한 문제를 풀 때마다 매번 헷갈리고 고생을 했어서 제대로 정리를 해봤다.

반복 숙달 해야겠다.