[#1992] 쿼드트리

RookieAND·2022년 6월 17일

백준 분할정복 재귀 코테

BaekJoon

목록 보기

19/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().strip())) for _ in range(N)]


def seperate(start_x, start_y, end_x, end_y):
    # 함수를 시작하기 전, 탐색의 시작점으로 ( 를 출력시킨다.
    value = matrix[start_y][start_x]
    # 만약, 탐색 범위가 1칸이라면, 값을 출력시키고 탐색 종료
    if start_x == end_x and start_y == end_y:
        print(value, end='')
        return
    is_same = True
    # 탐색 영역에 든 값이 동일한지를 판별해야 하기에, 이중 for 문 실행.
    for y in range(start_y, end_y + 1):
        if not is_same: break
        for x in range(start_x, end_x + 1):
            if matrix[y][x] != value:
                is_same = False
                break

    # 색상이 동일하다면 값만 출력시키고, 그렇지 않을 경우 분할 정복 시행.
    if is_same:
        print(value, end='')
    # 분할해야 할 경우 괄호를 씌워야 하므로 앞 뒤로 괄호를 열고 닫음.
    else:
        print('(', end='')
        mid_x, mid_y = (start_x + end_x + 1) // 2, (start_y + end_y + 1) // 2
        seperate(start_x, start_y, mid_x - 1, mid_y - 1)
        seperate(mid_x, start_y, end_x, mid_y - 1)
        seperate(start_x, mid_y, mid_x - 1, end_y)
        seperate(mid_x, mid_y, end_x, end_y)
        print(')', end='')

seperate(0, 0, N-1, N-1)