[백준/BOJ] 백준 코딩 알고리즘 2630번 색종이 만들기 Python 분할 정복

나의 풀이

 

이 문제는 재귀를 이용한 분할 정복으로 풀 수 있다

 

우선 파란색 종이냐, 하얀색 종이냐, 혹은 아직 더 잘라야하는 종이인가를 판별하는 알고리즘을 짜야한다

이를 구현하려면, 길이가 n일 때 너비가 n^2임을 고려하여, 너비 영역의 합이 n^2임을 확인한다

 

만약 n^2인 경우 파란색으로 칠해진 종이이며, 파랑 카운트를 1 올린다

만약 0인 경우 하얀색으로 칠해진 종이이며, 하양 카운트를 1 올린다

그 외의 경우에는 아직 섞여 있는 것이기 때문에 종이를 더 자르도록 탐색을 진행한다

 

그러면 어떻게 나누어서 탐색을 해야할까?

 

그에 대해서는 다음과 같이 정리할 수 있다

정사각형의 색종이가 있을 때, N/2를 통해서 중간 지점을 구하여 4분할을 할 수 있다

 

그리고 위 그림에서 노란색으로 동그라미 친 부분을 각 분할 정복을 시작할 시작점이라고 생각하고

가로, 세로로 N/2씩 전진하여 영역값을 다시 탐색하면 된다 -> 재귀 호출

 

이를 코드로 간단히 정리하면 아래와 같이 나타낼 수 있다

 

 

너비합을 구하고

그 너비합의 값에 따라서 if문을 사용해 분기를 나눈다

그리고 else (아직 더 나눠야 하는) 경우에는 재귀 호출을 통해 분할 탐색을 이어가도록 한다

 

이를 코드로 구현하면 아래와 같다

 

import sys
sys.setrecursionlimit(1000000)

def input():
  return sys.stdin.readline().rstrip()

N = int(input())
papers = [list(map(int, input().split())) for _ in range(N)]

blue_cnt = 0
white_cnt = 0

def divide_n_conquer(x: int, y: int, n: int):
  # 부분합 계산
  total = 0
  for i in range(n):
    total += sum(papers[x + i][y:y + n])

  # 부분합 값에 따른 판별
  if total == n**2:
    global blue_cnt
    blue_cnt += 1
    return
  elif total == 0:
    global white_cnt
    white_cnt += 1
    return
  else:
    half = n // 2
    divide_n_conquer(x, y, half)
    divide_n_conquer(x, y + half, half)
    divide_n_conquer(x + half, y, half)
    divide_n_conquer(x + half, y + half, half)

divide_n_conquer(0, 0, N)
print(f"{white_cnt}\n{blue_cnt}")