[Python] 색종이 만들기 - 백준 (분할정복)

해당 글은 백준 2630번 문제 '색종이 만들기'을 다룬다.

문제

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

2630번: 색종이 만들기

 

설명

해당 문제는 쪼개진 사각형안에 포함된 color가 다른 게 있다면,

재귀 함수를 통해서 N//2 씩 계속해서 나누어서 해결할 수 있다.

주의할 점은 재귀함수 4번 호출하는 구간에서 마지막에 return을 해주어서 재귀함수를 종료하게 해주어야 한다.

 

코드

n = int(input())

arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

def solution(x, y, N):
    global white, blue
    color = arr[x][y]
    for i in range(x, x + N):
        for j in range(y, y + N):
            if color != arr[i][j]:
                solution(x, y, N // 2)
                solution(x, y + N // 2, N // 2)
                solution(x + N // 2, y, N // 2)
                solution(x + N // 2, y + N // 2, N // 2)
                return

    if color == 0:
        white += 1
    else:
        blue += 1

white, blue = 0, 0
solution(0, 0, n)
print(white)
print(blue)