[백준] 2630번(색종이 만들기) with Python

문제

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

풀이

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

첫 색상이 나머지 색상과 같은지 확인 후 틀린 것이 있으면, 틀린 구역을 다시 네 구역으로 나누어 다시 색상이 같은 것을 확인해주기 위해 재귀를 이용해서 풀었다. 

재귀 호출시 들어가야하는 인수의 값이 헷갈려서 그림으로 시작점을 표시해보았다.

비슷한 문제

[백준] 1992번(쿼드트리) with Python

답

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