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

 

목차

개요

1030번: 프렉탈 평면 (acmicpc.net)

1030번: 프렉탈 평면

정해진 횟수 s만큼 프랙탈 동작을 한다. 이 프랙탈 동작은 현재 주어진 공간을 n*n으로 분할하고, 그 중 k*k에 해당하는 중앙 부분을 검은색으로 칠하는 행위이다. 
이런 s,n,k가 주어지고 또 출력하고 싶은 프랙탈의 공간 부분이 주어진다. 원하는 부분을 출력하면 된다.

풀이

프랙탈 동작은 공간이 쪼개지고 그 쪼개진 공간에 대해 다시 프랙탈 동작을 이어나간다. 즉 문제가 부분으로 쪼개지고, 각 부분이 전체에 대해 이뤄진 동작과 같은 수행을 한다는 것. 부분 문제로 쪼갤 수 있고, 같은 수행을 한다는 것은 재귀로 풀 수 있다는 것을 뜻한다.

이렇게 공간을 활용하는 재귀 문제에 대해 가장 쉬운 접근법 중 하나는 활용되는 모든 공간을 리스트나 배열로 선언한 후에 내가 원하는 공간의 위치를 인덱스로 접근하는 것이다. 
이 문제 역시 그렇게 접근할 수 있다. 그렇다면 전체 공간은? 한 변은 매 시행마다 n으로 분할되고, 그것이 s번 반복된다. 즉 한 변을 $n^s$로 하는 정사각형 만큼의 공간이 필요하다는 뜻이 된다. 
문제 제한을 보면 n의 최대값은 8, s의 최대값은 10이니까 최대 $8^{10}$의 공간이 필요하게 되는데, 이는 대충 $2^{30}$이고, $1024^{3}$이니까 대충 10억이 넘는 공간이 필요하다는 이야기가 된다;

당연히 메모리 초과가 뜬다. 하지만 일단 이 접근법으로 어떻게 풀 수 있는지 끝까지 아이디어를 개진해보자.

메모리 초과가 뜨는 코드는 다음과 같다.

s,n,k,r1,r2,c1,c2 = map(int, input().split())
size = n ** s
paint = (n-k) // 2
lst = [[0] * size for _ in range(size)]

def recur(t,x,y,color):
    if t == 1:
        if color:
            lst[x][y] = 1
        return
    tmp = t//n
    for i in range(n):
        for j in range(n):
            if (paint <= i < paint + k) and (paint <= j < paint + k) or color:
                recur(tmp, x + tmp * i, y + tmp * j, 1)
            else:
                recur(tmp, x + tmp * i, y + tmp * j, 0)

recur(size, 0,0,0)
for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        print(lst[i][j], end='')
    print()

size는 전체 공간의 크기를 가늠하기 위해 사용되는 변수. paint는 n*n으로 쪼갤 때 그 쪼개지는 공간 중 어느 부분을 색칠해야 하는지를 나타내는 변수이다. 만약 n이 5라면 5 * 5의 부분이 생길텐데 k가 3이라면 가운데 3 * 3의 공간이 검게 칠해져야 할 것이다. 그러면 어느 인덱스부터 검게 칠해질 것이냐, 5-3을 2로 나눈 값인 1이 처음 검게 칠해지기 시작할 위치 인덱스라는 것.

재귀를 돌면서 프랙탈 동작을 한다. 코드 상으로는 사실 이미 전부 분할된 공간에 칠하는 행위만 하러 들어가는 것이다. color가 1로 들어오면 그때 돼서야 칠하는 방식. x y를 통해 프랙탈 동작을 할 공간의 0, 0 지점을 나타내는데, tmp를 통해 각 부분의 x, y가 어디인지를 조절한다. 

아주 기본적인 공간에 대한 재귀적 접근 방법. 위에서 말했듯이 이 풀이는 메모리 초과가 난다.

s,n,k,r1,r2,c1,c2 = map(int, input().split())
size = n ** s
paint = (n-k) // 2
lst = [[0] * (c2-c1+1) for _ in range(r2-r1+1)]

def recur(t,x,y,color):
    if t == 1:
        if color and r1 <= x <=r2 and c1 <= y <=c2:
            lst[x-r1][y-c1] = 1
        return
    tmp = t//n
    for i in range(n):
        for j in range(n):
            if (paint <= i < paint + k) and (paint <= j < paint + k) or color:
                recur(tmp, x + tmp * i, y + tmp * j, 1)
            else:
                recur(tmp, x + tmp * i, y + tmp * j, 0)

recur(size, 0,0,0)
for i in lst:
    print(*i, sep='')

다음으로 도전한 코드는 이렇다. 어차피 내가 출력할 곳은 r1부터 r2까지의 행, c1부터 c2까지의 열이다. 그렇다면 메모리를 전부 사용하지 말고, 해당 부분에 대해서만 사용하면 어떨까? 재귀 동작은 전부 그대로 한다. 그러나 색칠을 하는 파트에서 내가 출력할 부분에 해당되는지 체크한다. 출력할 부분이면서 색깔을 칠해야 하는 부분이라면 색을 칠한다. 
아주 조금 더 생각을 개진한 것이다.

그러나 이건 시간 초과 판정을 받는다.. 위 코드는 분명 문제가 없다. 그러나 내가 출력할 부분이 정해져 있어서 그쪽 공간에 대해서만 따질 것이라면, 내가 출력하지 않을 부분에 접근했을 때 그 이상 재귀를 돌 필요가 없다. 내가 출력할 곳에 대해서만 재귀들 돌면 된다는 것이다. 그래서 이를 조건으로 걸어서 재귀를 돌게 만들면 된다. 

코드

s,n,k,r1,r2,c1,c2 = map(int, input().split())
size = n ** s # 프랙탈의 전체 크기
paint = (n-k) // 2 # 프랙탈 동작 시 처음 색칠하게 될 부분의 인덱스
lst = [[0] * (c2-c1+1) for _ in range(r2-r1+1)]

def recur(t,x,y,color):
    if t == 1:
        if color and r1 <= x <= r2 and c1 <= y <= c2:
            lst[x-r1][y-c1] = 1
        return
    tmp = t//n # 인덱스 뛰는 단위. 재귀를 돌 때마다 작아짐.
    for i in range(n):
        for j in range(n):
            if (r1 <= x + tmp * i <= r2) or (r1 <= x + tmp * (i+1) <= r2) or (x + tmp * i <= r1 and x + tmp * (i+1) >= r2 ): # 이것과 아래 if문은 접근 3에서 추가한 코드.
                if (c1 <= y + tmp * j <= c2) or (c1 <= y + tmp * (j+1) <= c2) or (y + tmp * j <= c1 and y + tmp * (j+1) >= c2 ):
                    if (paint <= i < paint + k) and (paint <= j < paint + k) or color: # 색칠할 곳 판정
                        recur(tmp, x + tmp * i, y + tmp * j, 1) #1을 넣으면 검게 칠할 곳
                    else:
                        recur(tmp, x + tmp * i, y + tmp * j, 0) #0을 넣으면 냅둠

recur(size, 0,0,0)
for i in lst:
    print(*i, sep='')

조건이 조금 복잡하다. 내가 현재 접근한 인덱스가 r1과 r2의 사이인지를 체크해야 한다. 현재 재귀를 돌고 있는 공간이 출력할 공간보다 작다면 당연히 그리 해야 할 것이다. 그런데 그렇지 않은데도 재귀를 돌아야 하는 경우가 있다. 바로 현재 재귀를 도는 공간이 출력할 공간보다 큰 경우이다. 요컨대 현재 재귀를 따지려는데 r1과 r2가 현재 재귀를 돌려는 공간 안에 있다면, 당연히 재귀를 돌아야 할 것이다. 따라서 위의 귀찮도록 긴 조건문이 나오게 된다..

이것보다 조금 더 깔끔한 접근 방법도 있다. 메모리를 따로 마련할 필요 없이, 현재 출력할 부분들에 어디를 검게 칠해야 하는지 검사만 하면 된다. 즉 순회하면서 재귀를 호출하여 해당 위치에서 0을 출력할지, 1을 출력할지 정한다는 것이다.

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

def recur(t,x,y):
    if t == 1:
        return 0
    tmp = t // n
    if (tmp * (n-k)//2 <= x < tmp * (n+k)//2) and (tmp * (n-k)//2 <= y < tmp * (n+k)//2):
        return 1
    return recur(tmp,x%tmp,y%tmp)

for i in range(r1, r2+1):
    for j in range(c1, c2+1):
        print(recur(size, i,j), end='')
    print()

생각을 조금만 바꾸면 코드를 더 깔끔하게 작성할 수 있게 된다. 재귀를 통해 각 단계에서 검게 칠해야 하는 부분으로 판정되는지 확인한다. 그리고 다음 단계로 넘어가려면 칠해지지 않은 부분이어야 한다. 이때 tmp로 좌표를 나누는 것을 확인할 수 있는데,

저렇게 하지 않으면 이런 결과가 나온다. 무슨 뜻이냐, 단계를 넘어가면서 확인을 하는 건 좋은데 조건문으로 확인하는 범위와 좌표가 스케일링이 되지 않는다는 것이다. 이를 해결하는 간단한 방법은 그냥 좌표를 스케일링하는 것이고, 그래서 나머지 연산을 해주는 것이다!

참고로 이 방법은 모든 좌표들에 대해 확인을 하기 때문에 시간이 조금 더 걸린다.