[Algorithm] 분할 정복(Divide & Conquer)

분할 정복

 

  크고 방대한 문제를 쉽게 풀 수 있는 문제 단위로 나누고, 그것들을 다시 합쳐서 문제를 해결하는 방법이다. 일반적으로 재귀 함수를 통해 구현하며, 메모리 제한이 없다면 비교적 빠르게 문제를 해결할 수 있다. 부분 문제가 다른 부분 문제에 영향을 미치지 않는다. (DP의 경우 영향을 미친다.)

1. Divide: 기존 문제를 작은 문제로 나눈다. → 큰 문제를 어떻게 나눌 것이고, 이 과정의 최종 목표는 무엇인가?
   1. Base Case: 더 작은 부분의 문제로 나누지 않아도 바로 답을 구할 수 있는 경우
   2. Recursive Case: 같은 형태의 부분 문제로 쪼개야 하는 경우
2. Conquer: 나누어진 문제가 여전히 분할이 가능하면 또 다시 Divide를 수행하고, 그렇지 않으면 문제를 해결한다.
3. Combine: 해결한 부분 문제들을 합쳐서 기존 문제를 해결한다.

 

---

 

2630번: 색종이 만들기

 

🥕 문제

  여러 개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2 색종이로 나눈다. 나누어진 종이 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

 

🥕 분석

• 큰 문제를 어떻게 나눌 것인가? → 정사각형 색종이를 똑같은 크기의 4개의 색종이로 나눈다.
• 분할 과정의 최종 목표는 무엇인가? → 잘라진 종이가 모두 하얀색 또는 파란색으로 이루어지도록 한다.

1. Divide
   1. Base Case: 잘라진 종이가 모두 하얀색 또는 파란색일 때
   2. Recursive Case: 정사각형의 좌표 (0, 0)과 다른 색의 좌표가 존재할 경우
2. Conquer: 현재 정사각형의 (0, 0) 좌표의 색을 리스트에 넣어 둔다. 또 다시 분할이 가능할 경우 정사각형 색종이를 똑같은 크기의 4개의 색종이로 나눈다.
3. Combine: 리스트에서 하얀색과 파란색의 값을 각각 count 한다.

 

🥕 풀이

n = int(input()) # 전체 종이의 한 변의 길이
paper = [list(map(int, input().split())) for _ in range(n)]

answer = []
def cut(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]:
                # 구역을 사분면으로 나눠서 탐색
                cut(x, y, n // 2)
                cut(x, y + n // 2, n // 2)
                cut(x + n // 2, y, n // 2)
                cut(x + n // 2, y + n // 2, n // 2)
                return
    if color == 0: # white
        answer.append(0)
    else: # blue
        answer.append(1)

cut(0, 0, n)
print(answer.count(0))
print(answer.count(1))