백준 | 1780 - 종이의 개수 (python)

📄 종이의 개수

9등분으로 분할하는 분할정복 문제

 

 

---

✏️ 문제

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

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

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

 

입력

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

 

출력

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

 

 

---

💡 해결방법

분할 정복이 대표적으로 4등분을 하는 문제였다면, 이 문제는 9등분으로 분할하는 문제이다.

 

기존 4등분 문제는 배열에 0, 1만 있어서 1인 것만 찾아서 count를 올려줬는데 이 문제는 -1, 0, 1 모두 있어서 그렇게 하기엔 한계가 있었다. 그래서 가장 첫번째 숫자를 target으로 잡고, target과 배열의 모든 수가 같으면 해당 숫자를 count 하는 방식을 선택했다.

 

만약 가장 첫번째 숫자인 target과 다른 수가 나오게 된다면 그 종이는 쓸 수 없으므로 9등분으로 나누어야 한다. 분할 정복은 재귀를 이용하므로 재귀 함수를 호출했다.

 

paper(n, r, c) 는 다음과 같이 돌아간다.

n은 배열의 길이, r은 배열의 첫번째 행, c는 배열의 첫번째 열이 함수의 인수로 들어간다.

d[r][c] 즉 분할된 배열의 가장 첫번째 수가 target이 된다.

분할된 배열을 돌면서 target과 다른 수가 나온다면 재귀 함수를 호출한다. -> 9등분을 하는 것

 

이때 r,c는 분할된 배열의 첫번째 행과 첫번째 열이라고 했으므로 분할 됐을 때의 첫번째 행과 첫번째 열을 넣어주면 된다.

9개로 분할하면 9개의 각각 사각형 중 첫번째 행과 첫번째 열은 위와 같이 9개가 나오게 될 것이다.

r,c에 알맞게 넣어준 함수를 호출하면 된다.

함수가 총 9개 호출하는데 이는 반복문으로도 코드를 깔끔하게 쓸 수 있으나 시간이 좀 더 걸려서 그냥 일일히 썼다.

 

만약 배열을 돌면서 target과 배열의 모든 수가 같다면 target에 해당하는 숫자를 1씩 올려준다.

 

 

👩🏻‍💻 소스코드

# 1780 : 종이의 개수

import sys

n = int(sys.stdin.readline())
d = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
one = 0
zero = 0
minus = 0


def paper(n, r, c):
    global one
    global zero
    global minus
    target = d[r][c]
    for i in range(r, r+n):
        for j in range(c, c+n):
            if d[i][j] != target:
                # 함수 호출을 다음과 같은 반복문으로도 가능
                # for x in range(3):
                #     for y in range(3):
                #         paper(n//3, r+(n//3 * x), c+(n//3 * y))
                paper(n//3, r, c)
                paper(n//3, r, c+n//3)
                paper(n//3, r, c+2*(n//3))
                paper(n//3, r+n//3, c)
                paper(n//3, r+n//3, c+n//3)
                paper(n//3, r+n//3, c+2*(n//3))
                paper(n//3, r+2*(n//3), c)
                paper(n//3, r+2*(n//3), c+n//3)
                paper(n//3, r+2*(n//3), c+2*(n//3))
                return

    if target == 0:
        zero += 1
    elif target == -1:
        minus += 1
    elif target == 1:
        one += 1


paper(n, 0, 0)
print(minus)
print(zero)
print(one)

 

---

 

 

1780번: 종이의 개수