[백준] 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

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

예제 출력 1

10
12
11

참고 답안

import sys
N = int(sys.stdin.readline())
numbers, answer = [], [0, 0, 0]

for i in range(N):
    line = list(map(int, sys.stdin.readline().split(' ')))
    numbers.append(line)

def count(start_row, start_col, length):
    if length == 1:
        answer[numbers[start_row][start_col] + 1] += 1
        return

    first = 0
    for i in range(start_row, start_row+length):
        for j in range(start_col, start_col+length):
            if i == start_row and j == start_col:
                first = numbers[i][j]
                print(f'first : {i, j, first}')
                continue
            else:
                if numbers[i][j] != first:
                    second_len = int(length/3)
                    print(f'재귀하러 들어옴 : {i,j}')
                    for k in range(start_row, start_row + length, second_len):
                        for l in range(start_col, start_col + length, second_len):
                            count(k, l, second_len)
                    return
            print('해당 없음')
    answer[first + 1] += 1
    print(f'answer : {answer}')
count(0, 0, N)
print(answer[0])
print(answer[1])
print(answer[2])

1. 우선 종이를 담을 리스트와 -1,0,1의 개수를 담을 리스트를 만든다.
2. 값을 받는다.
   1. 여기서 input = sys.stdin.readline 을 쓰면 나중에 /n 오류가 떠서 input대신 바로 sys~를 하였다.
3. 재귀함수를 만든다.
   1. 우선 길이가 1이면 종이가 하나이기 때문에 입력받은 값에 1을 더해서 해당 숫자 인덱스를 가진 거에 1을 더한다. -1,0,1이기 때문에 1을 더해야 0,1,2 인덱스가 되기때문이다.
   2. 그 다음에 길이가 1이 아니면 이중 for문을 돈다.
      1. 처음 행과 열의 숫자가 함수에 입력된 값과 같으면 시작값 (-1,0,1) 중에 해당되는 것으로 설정한다.
      2. 다르면 그 다음에 돌때 길이를 설정한다. 3의 제곱이라했기에 3으로 나눠서 길이를 설정한다.
      3. 위에서 나눈 길이로 다시 함수를 돌린다.
         1. 그러면 9는 3,1로 돌면서 해당되는 종이의 개수를 찾는다.
   3. 이렇게 다 돌고 first에서 1을 더해준다.
4. 마지막으로 answer를 출력한다.

이해하려고 출력한 값들

i, j (0, 0)
first : (0, 0, 0)
i, j (0, 1)
해당 없음
i, j (0, 2)
해당 없음
i, j (0, 3)
재귀하러 들어옴 : (0, 3)
i, j (0, 0)
first : (0, 0, 0)
i, j (0, 1)
해당 없음
i, j (0, 2)
해당 없음
i, j (1, 0)
해당 없음
i, j (1, 1)
해당 없음
i, j (1, 2)
해당 없음
i, j (2, 0)
해당 없음
i, j (2, 1)
해당 없음
i, j (2, 2)
해당 없음
answer : [0, 1, 0]
i, j (0, 3)
first : (0, 3, 1)
i, j (0, 4)
해당 없음
i, j (0, 5)
해당 없음
i, j (1, 3)
해당 없음
i, j (1, 4)
해당 없음
i, j (1, 5)
해당 없음
i, j (2, 3)
해당 없음
i, j (2, 4)
해당 없음
i, j (2, 5)
해당 없음
answer : [0, 1, 1]
i, j (0, 6)
first : (0, 6, -1)
i, j (0, 7)
해당 없음
i, j (0, 8)
해당 없음
i, j (1, 6)
해당 없음
i, j (1, 7)
해당 없음
i, j (1, 8)
해당 없음
i, j (2, 6)
해당 없음
i, j (2, 7)
해당 없음
i, j (2, 8)
해당 없음
answer : [1, 1, 1]
i, j (3, 0)
first : (3, 0, 1)
i, j (3, 1)
해당 없음
i, j (3, 2)
해당 없음
i, j (4, 0)
해당 없음
i, j (4, 1)
해당 없음
i, j (4, 2)
해당 없음
i, j (5, 0)
해당 없음
i, j (5, 1)
해당 없음
i, j (5, 2)
해당 없음
answer : [1, 1, 2]
i, j (3, 3)
first : (3, 3, 0)
i, j (3, 4)
해당 없음
i, j (3, 5)
해당 없음
i, j (4, 3)
해당 없음
i, j (4, 4)
해당 없음
i, j (4, 5)
해당 없음
i, j (5, 3)
해당 없음
i, j (5, 4)
해당 없음
i, j (5, 5)
해당 없음
answer : [1, 2, 2]
i, j (3, 6)
first : (3, 6, 0)
i, j (3, 7)
해당 없음
i, j (3, 8)
해당 없음
i, j (4, 6)
해당 없음
i, j (4, 7)
해당 없음
i, j (4, 8)
해당 없음
i, j (5, 6)
해당 없음
i, j (5, 7)
해당 없음
i, j (5, 8)
해당 없음
answer : [1, 3, 2]
i, j (6, 0)
first : (6, 0, 0)
i, j (6, 1)
재귀하러 들어옴 : (6, 1)
i, j (6, 3)
first : (6, 3, 0)
i, j (6, 4)
재귀하러 들어옴 : (6, 4)
i, j (6, 6)
first : (6, 6, 0)
i, j (6, 7)
재귀하러 들어옴 : (6, 7)
10
12
11