[#1780] 종이의 개수

RookieAND·2022년 6월 21일

BaekJoon

목록 보기

21/42

❓ Question

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

📖 Before Start

분할 정복을 기반으로 하되, 분할의 범위를 신중히 결정해야 하는 문제.

이번 문제는 분할 정복과 BFS 탐색을 사용하여 풀어야 하는 문제였다.
처음 분할 정복에 쓰일 범위를 지정하는 과정에서 꽤나 애를 먹었지만,
결국 몇 번의 시도 끝에 정답 처리를 얻어내었다.

✒️ Design Algorithm

이번 분할 정복은 범위를 9개로 쪼개서 풀어야 하는 문제였다.

N X N 크기의 이차원 배열 안에 0 과 1 이 골고루 분포되어 있다.
이번엔 N 이 3의 제곱수이며, 최댓값은 3의 7제곱 까지 가능하다고 한다.

이차원 배열을 좌표 평면이라 가정하고, 탐색을 시작할 정점 한 개를 지정한다.
정점 (x1, y1) 과 탐색 범위인 M 을 지정한 후, 탐색을 종료할 정점을 구한다.
만약 탐색 영역 내 색상이 모두 같다면 각 종이의 수량을 1씩 증가시킨다.
영역 내의 색상이 다르다면, 탐색 영역을 94분할 하여 각각의 영역을 다시 탐색한다.

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

시작 정점 (x1, y1) 과 종료 정점 (x1 + M - 1, y1 + M - 1) 을 3등분 한다.
그 후, 각 영역에 따른 시작 정점을 9개 구하고, 탐색 범위를 3 으로 나눈다.

💻 Making Own Code

✅ Correct Code

import sys
sys.setrecursionlimit(10 ** 5)

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

# 색종이의 수량을 담을 Dictionary 생성.
result = {-1: 0, 0: 0, 1: 0}


def divide(x, y, n):
    value = matrix[y][x]
    for loc_y in range(y, y + n):
        for loc_x in range(x, x + n):
            # 만약 값이 다른 영역이 있다면, 분할 정복을 진행.
            if matrix[loc_y][loc_x] != value:
                # 여기서부터는 분할을 진행하므로, 카운트하지 않아야 함.
                for len_y in range(3):
                    for len_x in range(3):
                        divide(x + len_x * (n // 3), y + len_y * (n // 3), n // 3)
                # 재귀 함수를 호출하였다면 함수를 종료해야 함. return
                return

    result[value] += 1
    return


divide(0, 0, N)
print(*(result[-1], result[0], result[1]), sep='\n')