[백준] 재귀함수_2630 색종이 만들기

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

2630번: 색종이 만들기

 

이 문제는 분할 정복을 이용해서 푼다.

- 분할 정복 : 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식

 

solution(x,y,N) 를 호출하여 색종이의 (x,y) 번째 부터 (x+N,y+N) 까지 순회하면서 (x,y)의 색상과 다를 경우 

아래와 같은 순서대로 함수를 호출하는 과정을 반복한다. (색종이 반으로 잘라서 = N//2 확인)

• 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)

색상이 모두 같다면 0일 경우, 1일 경우 구분하여 리스트에 추가한다.

 

import sys

N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] 

result = []

def solution(x, y, N) :
  color = paper[x][y]
  
  for i in range(x, x+N) :
    for j in range(y, y+N) :
      if color != paper[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 :
    result.append(0)
  else :
    result.append(1)


solution(0,0,N)
print(result.count(0))
print(result.count(1))