[백준 1780번] 파이썬 - 종이의 개수

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

1780번: 종이의 개수

 

 

# 조건

• N x N 크기의 행렬로 표현되는 종이
• -1, 0, 1 중 하나가 저장
• 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용
• 위의 경우가 아닌 경우 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘리 종이에 대해서 위의 과정을 반복
• -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하라
• N(1<=N<=3^7)

 

 

 

# 접근 방법

• 큰 부분부터 시작위치의 숫자를 기준으로 순회한다.
• 크기가 3^k로 진행되므로 9등분 되는 규칙은 3으로 나눠주면 된다.
• 숫자가 다르다면 n//3 으로 쪼개지는 규칙에 의거하여 재귀로 탐색해준다.
• 즉, dfs와 비슷하게 처음 크기 9를 탐색 중 숫자가 불일치 9등분 -> 나눠진 종이의 크기 = 9//3
• 왼쪽위의 3x3 크기의 종이부터 탐색 -> 일치한다면 넘어가고 불일치시 9등분 -> 나눠진 종이의 크기 = 3//3

 

• 제일 작은 사각형 = 1 이라면 +1,
• 또한 현재 3^x 크기의 사각형이 모두 같은 크기라면 +1

 

 

import sys  
sys.stdin = open('input.txt')  
  
# x, y, 현재 사각형 크기  
def paper(r,c,n):  
    global arr, count  
    # 시작위치 숫자 기준으로 잡아준다.  
    pivot = arr[r][c]  
    flag = False  
    # 제일 작은 크기의 종이 == 1 이 되었다면 +1    if n==1:  
        count[pivot-2] += 1  
        return 0  
    # 시작점 -> 전체 크기 까지  
    for i in range(r, r+n):  
        for j in range(c, c+n):  
            # 기준 숫자와 같이 않다면 세분화 시켜준다.  
            if arr[i][j] != pivot:  
                # 시작부터 -> 시작 + 크기까지 -> 크기//3 만큼 등분시켜서 반복  
                for y in range(r, r+n, n//3):  
                    for x in range(c, c+n, n//3):  
                        paper(y, x, n//3)  
                flag = True  
                break  
        if flag:  
            break  
    # 정상종료시 ( 다 같은 숫자면)  
    else:  
        count[pivot-2] += 1  
        return 0  
  
  
N = int(input())  
arr = [[*map(int, input().split())] for _ in range(N)]  
# 0, 1, -1  
count = [0,0,0]  
  
paper(0,0,N)  
print(*count, sep='\n')

 

• 간단한 재귀의 경우 나름 익숙 해졌지만, 아직 복잡한 로직을 재귀로 구현하는 것이 어렵다.
• 특히, 분할 정복의 경우 처음 시작하는 점과 같이 시작이 어려운 것 같다. 
• 더욱 의사코드와 로직의 중요성을 느끼는 중이다!