[백준/파이썬] 2630번: 색종이 만들기

문제

https://www.acmicpc.net/problem/2630

풀이

• 전체 종이의 크기 n
• 파란색 혹은 흰색 정사각형으로 채워져 있음
• 전체 종이가 같은 색으로 채워져 있지 않으면 4등분
• 잘라진 종이가 모두 같은 색이면 종료

분할 정복과 재귀를 활용하면 되는 문제

함수 선언

def func(x,y,n): # 시작점 (x,y)와 길이 n
	color = arr[x][y] # 시작점의 색

사각형 내에 다른 색이 있는지 검사

for i in range(x, x+n):
	for j in range(y, y+n):
    	if color != arr[i][j]:

만약 다른 색이 검출된다면 4등분 후 재귀

half = n//2
func(x, y, half)			# 1사분면
func(x+half, y, half)		# 2사분면
func(x, y+half, half)		# 3사분면
func(x+half, y+half, half)	# 4사분면
return # 분할이 끝나면 더 실행하지 않도록 return

검사 결과 모두 같은 색이면 결과 배열에 결과 추가

res.append(color)

코드

import sys
input = sys.stdin.readline

def func(x,y,n):
    color = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != arr[i][j]:
                half = n//2
                func(x, y, half)
                func(x+half, y, half)
                func(x, y+half, half)
                func(x+half, y+half, half)
                return
    res.append(color)

if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    res = []
    
    func(0,0,n)
    print(res.count(0))
    print(res.count(1))