(Python) - BOJ(1780번) : 종이의 개수

 

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

1780번: 종이의 개수

---

• 해설 : 

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

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

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

 

 

 

---

• 풀이 :

재귀를 이용한 분할정복 문제이다. 보드가 주어지면 보드를 9칸으로 나누어  모든 칸이 -1, 0, 1 의 값이라면 정답 카운트를 세고 재귀를 실행하지 않도록 구현하였다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
c1 = 0
c2 = 0
c3 = 0
 
 
def ans(x,y,n):
    global c1,c2,c3
    check = board[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if check != board[i][j]:
                ans(x, y, n // 3)
                ans(x, y + n // 3, n // 3)
                ans(x, y + (n * 2) // 3, n // 3)
                ans(x + n // 3, y, n // 3)
                ans(x + n // 3, y + n // 3, n // 3)
                ans(x + n // 3, y + (n * 2) // 3, n // 3)
                ans(x + (n * 2) // 3, y, n // 3)
                ans(x + (n * 2) // 3, y + n // 3, n // 3)
                ans(x + (n * 2) // 3, y + (n * 2) // 3, n // 3)
 
                return
    if check == -1:
        c1 += 1
    elif check == 0:
        c2 += 1
    else:
        c3 += 1
 
 
if __name__ == "__main__":
    N = int(input())
    board = [list(map(int,input().split())) for _ in range(N)]
    ans(0,0,N)
    print(c1)
    print(c2)
    print(c3)