[백준] 2630번 : 색종이 만들기 - Python(파이썬)

풀이

• 분할 정복
• 적절한 인덱싱을 통해 4분할 구현
• 모든 칸이 같은 색으로 사분할이 진행되지 않으면 갯수 추가

코드

import sys
input=sys.stdin.readline


def cut(n,x,y):
    global b,w
    color=array[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if color!=array[i][j]:
                cut(n//2,x,y)
                cut(n//2,x,y+n//2)
                cut(n//2,x+n//2,y)
                cut(n//2,x+n//2,y+n//2)
                return
    
    if color==0:
        w+=1
        return
    else:
        b+=1
        return


N=int(input())
array=[list(map(int,input().split())) for _ in range(N)]
w=0
b=0
cut(N,0,0)
print(w)
print(b)

 

헷갈렸던 점

#(1)blue와 white 갯수를 저장하는 변수 -> global 선언

def cut(n,x,y):
    global b,w
    
#사분할 분할 탐색 - 적절한 인덱싱으로 재귀 구현
for i in range(x,x+n):
	for j in range(y,y+n):
		if color!=array[i][j]: #한개라도 배열안에서 색깔이 다르면 사분할 진행
			cut(n//2,x,y)
			cut(n//2,x,y+n//2)
			cut(n//2,x+n//2,y)
			cut(n//2,x+n//2,y+n//2)