백준 2630 색종이 만들기

문제

색종이 만들기

2k 길이를 갖는 정사각형 색종이 개수를 구하자

난이도 : Silver2

---

풀이

1. 재귀 함수로 사분면 탐색 구현
2. 파란색, 흰색을 구분해 계산

---

코드

import sys
from typing import List

N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
blue, white = 0, 0

def find(cut: List, length):
    global blue, white  # 전역 변수로 명시
    if len(cut[0]) == 1 or len(set([j for i in cut for j in i])) == 1:  # 배열 크기가 1이거나, 모든 배열 원소가 같은 숫자일 때
        if cut[0][0] == 0:
            white += 1
        else:
            blue += 1
    
        return  # return None이 없으면 이미 탐색되고 더 이상 탐색할 필요가 없는 색종이에 대해서 또 재귀가 돌아감

    length //= 2  # 길이를 2로 나눠 계속 탐색
    find([row[:length] for row in cut[:length]], length)  # 좌측 하단 탐색
    find([row[length:] for row in cut[:length]], length)  # 좌측 상단 탐색
    find([row[:length] for row in cut[length:]], length)  # 우측 하단 탐색
    find([row[length:] for row in cut[length:]], length)  # 우측 상단 탐색

    
find(paper, N)
print(white)
print(blue)