파이썬 / BOJ 백준 / 1780 종이의 개수 - 분할정복

파이썬 / BOJ 백준 / 1780 종이의 개수 - 분할정복

 

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

1780번: 종이의 개수

 

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

 

풀이

1. 이 문제는 분할정복으로 풀 수 있는 문제입니다. 

2. 조건이 만족하지 않는 경우(색상이 모두 같은 경우가 아닌 경우)는 9개로 쪼개서 다시 푸는 방식입니다.

3. 9개로 쪼개는 것은 재귀 함수를 호출하여 풀고, 전달인자로 그 9개의 각각 종이 중 가장 왼쪽 위의 좌표와 크기를 넣습니다.

4. 조건이 만족하는 경우(하나의 색상으로만 구성되는 경우)는 해당 색상의 값을 +1해줍니다.

전체 코드

N = int(input())

board = [list(map(int, input().split())) for _ in range(N)]

result_minus = 0
result_zero = 0
result_plus = 0


def dfs(x, y, n):
    global result_minus, result_zero, result_plus

    num_check = board[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if (board[i][j] != num_check):
                for k in range(3):
                    for l in range(3):
                        dfs(x + k * n // 3, y + l * n // 3, n // 3)
                return

    if num_check == -1:
        result_minus += 1
    elif num_check == 0:
        result_zero += 1
    else:
        result_plus += 1


dfs(0, 0, N)
print(f'{result_minus}\n{result_zero}\n{result_plus}')