[Python] BOJ 1780 : 종이의 개수

요구사항

1. 데이터의 개수 3**7 대략 2000개
2. 시간 제한 2초 대략 N**2 까지 가능
3. 메모리제한 : 256 * 10^6 바이트 
4. 종이가 모두 같은 수로 되어 있다면 그대로 사용
5. 그렇지 않을 경우 종이를 계속 잘라 같은 숫자만 남게 한다. 
6. 위와 같이 종이를 잘랐을 때, 각 숫자별 종이의 개수를 구해라. 

설계 

1. 종이의 크기를 결정할 K 를 입력 받는다.
2. K x K 크기의 종이를(2차원 배열) 받는다.
3. 종이에 적힌 숫자의 개수를 저장할 리스트를 초기화한다.
4. 사용자 정의 함수를 만든다.
   1. 초기값은 number = paper[x][y] = paper[0][0]
   2. for i in range(x, x+N), for j in range(y, y+N)
   3. 만약 number != paper[i][j]
      1. 사사분면에 대해 사용자 정의 함수를 실행한다.
      2. 총 9등분을 해야 한다. 따라서
      3. 아래와 같이 짜준다.
         
          for dx in range(3):

                             for dy in range(3):

                                 div(x + dx * K // 3, y + dy * K // 3, K // 3)
      4. 9등분의 좌표 이동:
         1. (x, y) -> 좌상단
         2. (x, y + K//3) -> 중상단
         3. (x, y + 2*K//3) -> 우상단
         4. (x + K//3, y) -> 좌중단
         5. (x + K//3, y + K//3) -> 중앙
         6. (x + K//3, y + 2*K//3) -> 우중단
         7. (x + 2*K//3, y) -> 좌하단
         8. (x + 2*K//3, y + K//3) -> 중하단
         9. (x + 2*K//3, y + 2*K//3) -> 우하단
   4. return 
5. 함수를 실행한다. div(0,0,K)
6. 각 숫자를 카운트해서 출력한다. 

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

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

result = []

def div(x, y, K):
    number = paper[x][y]

    for i in range(x, x + K):
        for j in range(y, y + K):
            if number != paper[i][j]:  # 종이 값이 다르면 9등분
                for dx in range(3):
                    for dy in range(3):
                        div(x + dx * K // 3, y + dy * K // 3, K // 3)
                return
    if number == 0:
        result.append(-1)
    elif number == 1:
        result.append(0)
    else:
        result.append(1)

div(0, 0, K)

print(result.count(1))
print(result.count(0))
print(result.count(-1))