[Python] 백준 2630 "색종이만들기_분할정복" 문제풀이

💡풀이과정

• 분할 단계
  • 하얀색과 파란색 종이의 수를 구하기 위해 (0~n/2,0~n/2), (n/2~n, 0~n/2), (0~n/2, n/2~n), (n/2~n, n/2~n) 구역을 4구역으로 나눠준다.
• 정복 단계
  • 해당구역의 종이가 모두 같은 색이면 합병단계로 넘어가고 해당구역의 종이가 모두 같은 색이 아니라면 다시 분할 단계로 넘어간다.
• 합병 단계
  • 해당 색깔의 종이의 수를 1씩 더해준다.

import sys

input = sys.stdin.readline

n = int(input())

paper= [list(map(int,input())) for _ in range(n)]

white, blue = 0

def divideAndConquer(x,y,n):
	global white,blue
    
    sameColor = paper[x][y]
    
    for i in range(x,x+n):
    	for j in range(y,y+n):
        	if sameColor != paper[i][j]:
            	divideAndConquer(x,y,n//2)
                divideAndConquer(x,y+n//2,n//2)
                divideAndConquer(x+n//2,y,n//2)
                divideAndConquer(x+n//2,y+n//2,n//2)
                return
                
    if sameColor == 0:
    	white += 1
    else:
    	blue += 1
        
divideAndConquer(0,0,n)
print(white)
print(blue)

💡피드백

• 결국 4구역으로 나누는 걸 계속 반복하니까 반복된 기능을 재사용할 수 있다는 점에 유리한 함수를 통해 4구역으로 만들어주는데 이때 해당 구역이 모두 같은 색이 아니라면 자기 자신을 또 4구역으로 나누어야 한다. (= 재귀함수)