백준 1030 프렉탈 평면 (파이썬)

https://www.acmicpc.net/status?from_problem=1&problem_id=1030 

채점 현황

문제

풀이

문제 이해를 시도하다가 도저히 안되어서 블로그를 참고했지만...이해하는데 오래 걸린 문제이다. 푸는데 이해를 하는데 고생을 한 만큼 글로 정리하고자 한다.

이 문제는 분할정복을 이용해서 푸는 문제로 재귀를 이용해서 풀었다.

문제를 푸는 순서는 다음과 같다.

1. 입력값들을 받는다.
2. 전체 프렉탈을 구성해 놓고 출력을 하는 것이 아닌 문제에서 원하는 지점에 대해서 검사를 한다. (전체 프렉탈을 구성할 경우 최대 2^30 * 2^30 인 프렉탈이 나오고 메모리 공간이 부족한 것은 물론 시간 복잡도 적인 측면에서 보아도 얻을 이점이 존재하지 않기 때문이다.)
3. 검사한 결과를 출력한다.

여기서 발목을 잡는 순서는 2번이라 생각된다.

2번, 즉 원하는 지점에 대한 검사를 하는 코드와 알고리즘은 다음과 같다.

• x, y는 검사하려는 좌표이다.
• block은 다음 시간대에서의 블럭 하나의 크기이다.
• l이 만약 1이라면 문제에서 주어진 조건에 의해서 하얀 영역이라고 판단한다.
• 현재 사각형에서 검은색 영역을 비율을 통해서 구하고 이 영역안에 x, y좌표가 존재하는지 확인한다.
  • 왼쪽 하얀색 영역 비율 : 중앙 검은색 영역 비율 : 오른쪽 하얀색 영역 비율
  • 즉 (N-K)//2 : K : (N-K)//2이다. 이를 좌표상으로 생각해보면 왼쪽과 오른쪽 영역의 시작 좌표는 다음과 같다. (N-K)//2, (N+K)//2

def check_board(l, point):
    x, y = point
    bolck = l//N # 다음 시간 기준 블럭 하나의 크기
    
    if l == 1: # 한 변의 길이가 1일때까지 탐색을 했음에도 값이 존재하지 않으면 하얀색이라고 판단
        return 0
    
    # block은 다음 시간대 기준 하나의 블럭 크기, (N-K)는 전체에서 검은색 영역을 뺀 길이 즉 하얀색 영역이다.
    # (N-K)//2, (N+K)//2는 왼쪽과 오른쪽 하얀색 영역이다.
    # 이때 비율을 통해서 block * (N-K)//2, block * (N+K)//2 구하고 해당 영역을 검은색 영역이라고 판단한다.
    if bolck * (N-K)//2 <= x < bolck * (N+K)//2 and bolck * (N-K)//2 <= y < bolck * (N+K)//2:
        return 1
    
   
    l = l//N # 현재 사각형의 길이을 다음 시간대의 길이에 맞게 스케일링한다.(축소)
    # 검사하려는 좌표를 다음 시간대의 사각형에 맞게 스케일링한다.(축소)
    x %= bolck 
    y %= bolck
    return check_board(l, (x,y))

 

 

 

전체 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

def check_board(l, point):
    x, y = point
    bolck = l//N
    
    if l == 1:
        return 0
    
    if bolck * (N-K)//2 <= x < bolck * (N+K)//2 and bolck * (N-K)//2 <= y < bolck * (N+K)//2:
        return 1
    
    l = l//N
    x %= bolck
    y %= bolck
    return check_board(l, (x,y))

s, N, K, R1, R2, C1, C2 = map(int, input().split())
l = N**s

for r in range(R1, R2+1):
    for c in range(C1, C2+1):
        print(check_board(l, (r, c)), end='')
    print()

참고

https://recordofwonseok.tistory.com/402#recentEntries

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