[알고리즘] BOJ 1780 종이의 개수 #Python

[BOJ] 1780 종이의 개수 바로가기

📍 문제

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

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

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

---

📍 입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

---

📍 출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

---

📍 풀이

🧷 풀이 과정

문제에서 주어진 규칙을 이용하여 알고리즘을 구현한다.

📒 1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

if check(x, y, N):
    answer[graph[y][x]] += 1
    return

def check(x, y, N):
    std = graph[y][x]
    for ny in range(y,y+N):
        for nx in range(x,x+N):
            if std != graph[ny][nx]:
                return False
    return True

• 종이(graph)의 x ~ x + N 구간, y ~ y + N 구간의 숫자가 모두 같다면 True 를 반환하고, 아닐 경우 False 를 반환한다.

📒 2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

else:
    N//=3
    for dy in range(3):
        for dx in range(3):
            divideConquer(x+N*dx, y+N*dy, N)

• 종이의 구간이 하나의 숫자가 아닌 여러 숫자가 섞여 있을 경우 종이를 9등분한다.

✍ 코드

# BOJ 1780 종이의 개수
# https://www.acmicpc.net/problem/1780

from sys import stdin

def solution(N, graph):
    answer = {-1: 0, 0: 0, 1: 0}

    # 종이가 모두 같은 수로 구성되어 있는가?
    def check(x, y, N):
        std = graph[y][x]
        for ny in range(y,y+N):
            for nx in range(x,x+N):
                if std != graph[ny][nx]:
                    return False
        return True

    # 분할 정복
    def divideConquer(x, y, N):
        if check(x, y, N):
            answer[graph[y][x]] += 1
            return
        # 같은 크기의 종이 9개로 분할
        N//=3
        for dy in range(3):
            for dx in range(3):
                divideConquer(x+N*dx, y+N*dy, N)

    divideConquer(0, 0, N)

    return answer.values()

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

result = solution(N, graph)
for res in result:
    print(res)