[#2630] 색종이 만들기

RookieAND·2022년 6월 17일

백준 분할정복 재귀 코테

BaekJoon

목록 보기

18/42

❓ Question

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

📖 Before Start

분할 정복과 재귀를 활용하는 문제를 찾아서 한번 풀어보려고 했다.

이번 문제는 분할 정복과 재귀 함수를 적절히 사용하여 알고리즘을 설계해야 했다.
처음으로 풀어보는 분할 정복 문제였지만, 그간 다른 문제를 풀면서 재귀에 대한 학습을
어느 정도 진행한 상태였기에 큰 부담 없이 문제 풀이에 임할 수 있었다.

✒️ Design Algorithm

분할 정복은 탐색 범위를 어떻게 쪼개느냐가 가장 큰 핵심이라고 생각한다.

N X N 크기의 이차원 배열 안에 0 과 1 이 골고루 분포되어 있다.
정말 다행이도 N 은 2의 제곱수이며, 최댓값은 2의 7제곱인 128 까지라고 한다.

이차원 배열을 좌표 평면이라 가정하고, 탐색을 진행할 두 정점을 지정한다.
두 정점 (x1, y1), (x2, y2) 사이의 영역을 순회하여 색상이 모두 같은지 판별한다.
만약 영역 내 색상이 모두 같다면 색종이의 수량을 1씩 증가시키고 함수를 종료한다.
영역 내의 색상이 다르다면, 탐색 영역을 4분할 하여 각각의 영역을 다시 탐색한다.

탐색 범위를 4분할 하는 방법은 아래와 같이 설계하였다.

두 정점 (x2, y2), (x1, y1) 에 대하여 x 와 y 좌표의 중간 값을 구한다.
그 후, 중간 값 (mid_x, mid_y) 을 기준으로 해당 영역을 4분할 시킨다.

💻 Making Own Code

✅ Correct Code

# 정사각형의 너비는 최소 1에서 최대 N까지 가능하다 (N은 2의 7승 미만)
# 1회에 최대 4번의 분할이 이루어지며, 각 영역에 다른 색상이 섞일 경우 재귀를 진행.
import sys
sys.setrecursionlimit(10 ** 5)

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

# 하얀색, 파란색 종이의 수량을 담는 변수 생성.
result = [0, 0]


# 탐색 시작 좌표와 끝 좌표를 구하고, 이를 분할하여 판별한다.
def seperate(start_x, start_y, end_x, end_y):
    color = matrix[start_y][start_x]
    # 만약 사각형의 각 변의 사이즈가 1이라면, 값을 추가시키고 재귀 종료.
    if end_y == start_y and end_x == start_x:
        result[color] += 1
        return

    is_same = True
    # 해당 영역을 이중 반복으로 탐색하여 다른 색상이 있는지 판별
    for y in range(start_y, end_y + 1):
        # is_Same이 false 일 경우 반복문을 즉시 탈출하도록 설계.
        if not is_same:
            break
        for x in range(start_x, end_x + 1):
            if matrix[y][x] != color:
                is_same = False
                break

    # 색상이 모두 같은 것으로 판명되었다면, 색상의 수량을 추가.
    if is_same:
        result[color] += 1
        return

    # 색상이 다르다면, 영역을 4개로 분할하여 탐색을 진행.
    mid_x = (start_x + end_x + 1) // 2
    mid_y = (start_y + end_y + 1) // 2
    # 만약 색상이 같지 않다면, 영역을 4분할 하여 분할 정복 시행.
    seperate(start_x, start_y, mid_x - 1, mid_y - 1)
    seperate(mid_x, start_y, end_x, mid_y - 1)
    seperate(mid_x, mid_y, end_x, end_y)
    seperate(start_x, mid_y, mid_x - 1, end_y)


seperate(0, 0, N-1, N-1)
print(*result, sep='\n')