[백준] 2630 색종이 만들기 파이썬 (분할정복)

문제

정사각형 색종이 한 칸에 1이나 0으로 모두 채워져있지 않으면 4등분 한다

 

문제 풀이

• 처음 입력 받은 값을 color_paper에 2차원 리스트로 저장한다.
• 맨 처음 [0][0] 원소를 check라고 두고 색종이를 다 돌면서 check와 같지 않은 부분이 있는 지 확인한다.
• 같지 않은 원소가 나타난 즉시 4등분한다
• if문에 안걸리고 4등분을 안하게 되면
• 그 check가 1인지 0인지 확인하고 white와 blue에 맞게 +1을 한다.

코드

import sys
n=int(sys.stdin.readline())
 
color_paper=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]#x행 y열
 
white=0#0이면 흰생
blue=0#1이면 파란색
 
def cut(x,y,n):
    global blue,white #전역변수
    check=color_paper[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if check!=color_paper[i][j]:#하나라도 같은색이 아니라면
                #4등분
                cut(x,y,n//2)#1사분면
                cut(x,y+n//2,n//2)#2사분면
                cut(x+n//2,y,n//2)#3사분면
                cut(x+n//2,y+n//2,n//2)#4사분면
                return
 
 
    if check==0:#모두 흰색일때
        white+=1
        return
    else:   #모두 파란색일때
        blue+=1
        return
 
 
cut(0,0,n)
print(white)
print(blue)