백준2630(파이썬) - 색종이 만들기

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

2630번: 색종이 만들기

• 이 문제 또한 요즘 내가 많이 풀고 있는 재귀를 이용한 문제이다.
• 분할정복을 사용하는 문제인데, 이런 문제는 보통 2^n 이나 3^n 의 형태로 나오고 4조각 혹은 9조각으로 나누어서 풀게 된다. 어려운 문제는 정사각형이 아닐...수는 있겠지만 그렇게되도 풀이가 완전 달라질꺼 같지는 않다.
• 2중 for문으로 2차원배열 graph를 순회하면서 처음 시작한 graph[i][j] 의 값과 달라질 때, 재귀를 이용해서 처음 주어지는 한 변의 길이 n을 1/2씩으로 쪼개서 한 변의 길이를 넘겨주는 방법을 생각했다.
• 처음 시작한 graph[i][j] (코드에서는 start로 정의해서 풀이하였다.) 가 1이면 흰색 카운트, 0이면 파란색 카운트를 올려주면서 개수를 파악하였다.

import sys
input = sys.stdin.readline

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
#하얀색 이 0 파란색이 1
white_cnt = 0
blue_cnt = 0

def functinon(x,y,length):
    global white_cnt,blue_cnt
    start = graph[x][y]
    for i in range(x,x+length):
        for j in range(y,y+length):
            if start != graph[i][j]:
                # 4개로 쪼갠다.
                for a in range(2):
                    for b in range(2):
                        functinon(x+length//2*a,y+length//2*b,length//2)
                return
    print(x,y)
    if graph[x][y] == 0:
        white_cnt += 1
    elif graph[x][y] == 1:
        blue_cnt += 1

functinon(0,0,n)
print(white_cnt)
print(blue_cnt)