봉건 시대 땐 왕이 영토를 쪼개 제후들에게 맡겼죠.

그럼 우리도 알고리즘 문제를 쪼개 재귀 함수들에게 맡기면 어떨까요?

그게 바로 분할 정복이랍니다!

분할 정복

• 아래와 같은 세 단계로 문제를 해결하는 방법
• 분할: 문제가 충분히 작아질 때까지 부분 문제로 나눔
• 정복: 나눈 부분 문제를 해결
• 조합: 부분 문제의 결과를 조합해, 원래 문제를 해결함

• 보통은 재귀함수를 이용해 구현

  • 함수 내 재귀 호출로 부분문제로 분할
  • 재귀 함수의 종료조건을 통해 부분문제를 정복
  • 아직 종료되지 않은 이전 함수로 돌아가, 결과를 조합

• 대표적 예시: 병합 정렬
  • 분할: 정렬할 배열을 앞 부분배열, 뒷 부분배열로 분할
  • 정복: 배열의 길이가 1인 경우, 이미 정렬된 상태
  • 조합: 정렬된 두 배열을 하나의 배열로 합침

• 물론 이것만 봐선 감이 잘 안 잡힐 거고...
• 실제로 문제를 풀어 보면서 감을 잡는 게 좋습니다

2630. 색종이 만들기

백준 / 실버 2 / 색종이 만들기

생각해봅시다!!

문제에서 분할 정복으로 풀어야 한다는 사실을 사실상 스포하고 있다.

• 목표: 잘라진 하얀색 색종이와, 파란색 색종이의 개수 구하기
• 분할: 가로와 세로로 중간 부분을 잘라서, 네 개의 종이로 나눈다
• 정복: 종이가 모두 하얀색 / 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 자를 수 없을 때까지
  • 사실상 칸이 하나 남으면 무조건 하양 혹은 파랑이니까, 그게 그 소리긴 함
• 조합: 정복을 통해 구한 하얀색 / 파란색 색종이 수를 다시 더하면 됨

재귀함수 만들기

재귀 함수는 목표에 맞게, 현재 종이 내 총 하얀색 색종이 및 파란색 색종이의 개수를 반환하게끔 만든다.

• 매개변수: 종이 한 변의 길이 N, 첫 칸의 좌표 x행 y열
• 반환값: (하얀색 색종이 수, 파란색 색종이 수)
• 종료 조건: 칸이 모두 하얀색/파란색일 때
  • 하얀색이면 (1, 0), 파란색이면 (0, 1)을 반환
• 분할 조건: 하얀색 칸, 파란색 칸이 섞여 있을 때
  • 종이를 4등분한 뒤, 각 부분에 대해 재귀함수 호출
  • 조합: 4등분한 종이의 내 하얀색 / 파란색 색종이 수를 모두 더한 뒤, 값을 반환

이런 재귀 함수를 만들면 아래 그림처럼 동작한다.

• 물론 실제 코테에서는 이렇게 노가다 하면서 그림을 그릴 순 없으니까, 보다 예리한 문제 분석력이 필요하다.

코드

N = int(input())
grid = []

for _ in range(N):
    grid.append(list(map(int, input().split())))

# 현재 종이 내 총 하얀색 / 파란색 색종이의 개수 세기
# N: 한 변의 길이
# 첫 칸 -> x행 y열
def check(N, x, y):
    # 모두 하얀칸 / 파란칸? 아님 섞여 있음?
    def find_color(N, x, y):
        # 첫 칸의 색
        color = grid[x][y]

        # 첫 칸과 불일치하는 색이 있는지 확인
        for i in range(x, x + N):
            for j in range(y, y + N):
                if grid[i][j] != color:
                    return -1 # 섞여 있음
        return color # 하얀칸은 0, 파란칸은 1

    color = find_color(N, x, y)

    if color == 0:        # 모두 하얀칸
        return 1, 0
    elif color == 1:      # 모두 파란칸
        return 0, 1
    else:                 # 하얀칸, 파란칸 섞임
        white, blue = 0, 0
        half = N // 2

        x_list = [x, x, x + half, x + half]
        y_list = [y, y + half, y, y + half]

        # 종이를 4등분
        # 4등분한 종이 내 하얀색 / 파란색 색종이 수 세기
        for i in range(4):
            cut = check(half, x_list[i], y_list[i])
            white += cut[0]
            blue += cut[1]

        return white, blue

result = check(N, 0, 0)
print(result[0])
print(result[1])

• find_color: 모든 칸이 하얀색 / 파란색인지, 색이 섞여 있는지 확인
  • 첫 칸의 색을 저장해 두기
  • 첫 칸과 다른 색의 칸을 발견하면 섞여 있다고 판단 가능
• 종이를 4등분할 땐 가운데 지점을 기준으로 자름
  • 따라서 변의 길이 // 2를 half로 둠
  • 왼쪽 위 사분면의 첫 칸 좌표는 x, y
  • 오른쪽 위 사분면의 첫 칸 좌표는 x, y + half
  • 왼쪽 아래 사분면의 첫 칸 좌표는 x + half, y
  • 오른쪽 아래 사분면의 첫 칸 좌표는 x + half, y + half
• 재귀호출된 함수가 반환한 cut은 (하얀종이 수, 파란종이 수)로 구성됨
  • white 변수에 cut[0]을
  • blue 변수에 cut[1]을 더하고
  • 두 값을 반환

시간 복잡도

• 종이의 한 변이 $N$일 때
  • 종이를 반절씩 자르기 때문에, 재귀의 최대 깊이는 $log_{2}N$
  • 각 깊이에서 check_color 함수가 여러 번 실행되며, 최악의 경우 전체 $N^2$칸을 모두 검사하므로 $O(N^2)$
• 최종 $O(N^2 \log N)$
• $N \leq 128$이며, $128 ^ 2 = 16,384$이므로 1초 내 연산 가능
  • $\log N$은 보통 무시할 정도로 작으므로, 사실상 $O(N^2)$