[Python] 백준 1780번 - '종이의 개수' 풀이

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

1780번: 종이의 개수

---

풀이

9를 입력받게 된다면, 9x9 배열을 만들게 되고, 모든 숫자가 같지 않을 때에 9개로 종이를 나눕니다.

나눈 종이에서의 모든 숫자가 같지 않은 경우 마찬가지로 해당 종이를 9개의 종이로 나누고 같지 않으면 또 나누는 문제입니다. 따라서 재귀함수를 이용할 수 있는 문제입니다.

재귀함수에서 진행할 내용은 1. 현재 종이가 모두 같은 수로 이루어져 있는지 , 2. 만약 1이 아니라면 9칸의 종이로 나누는 것 입니다.

def paper_div(x, y, n):
    global minus_one, zero, plus_one
    now_num = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if now_num != arr[i][j]:
                for k in range(3):
                    for l in range(3):
                        paper_div(x + k * n//3, y + l * n//3, n//3)
                return

    if now_num == '-1':
        minus_one += 1
    elif now_num == '0':
        zero += 1
    else:
        plus_one += 1

첫번째와 두번째 반복문은 진행사항 1번을 구현했습니다. 만약 같은 종이에 다른 숫자가 있다면, 해당 종이를 9칸으로 나눠 탐색하는 진행사항 2번으로 갑니다. 함수 안의 함수에 넣는 인자에는 쪼개진 종이의 x, y, n을 받았습니다. 안 함수의 탐색이 끝나면 return 으로 다시 함수로 돌아갑니다.

만약 모든 숫자가 같다면 해당 숫자인 now_num에 따라 각 수에 해당하는 전역변수(-1, 0, 1의 개수 저장)에 개수를 누적해줍니다.

import sys
N = int(sys.stdin.readline().rstrip())
arr = []
for i in range(N):
    arr.insert(i, sys.stdin.readline().rstrip().split())
minus_one = 0
zero = 0
plus_one = 0
def paper_div(x, y, n):
    global minus_one, zero, plus_one
    now_num = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if now_num != arr[i][j]:
                for k in range(3):
                    for l in range(3):
                        paper_div(x + k * n//3, y + l * n//3, n//3)
                return

    if now_num == '-1':
        minus_one += 1
    elif now_num == '0':
        zero += 1
    else:
        plus_one += 1
    
paper_div(0, 0, N)
print(f'{minus_one}\n{zero}\n{plus_one}')

---

후기

어려워서 여러 블로그를 찾아보고 코드를 짰습니다. 첫번째와 두번째 for문의 범위의 끝(x+n, y+n)에 대해 이해가 어려웠고,  안에 들어있는 함수의 인자를 이해하는 것도 어려웠습니다. 이 문제의 본질이었던 분할 정복과 재귀 함수에 대해 이해도를 확인할 수 있는 문제였던 것 같습니다.