[Python] 백준 1780 "종이의 개수_분할정복" 문제풀이

💡문제 풀이

import sys

input = sys.stdin.readline

n = int(input())

papers = [list(map(int,input().split())) for _ in range(n)]
a=0
b=0
c=0
def asdf(x,y,n):
    global a,b,c
    sameNum = papers[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if sameNum != papers[i][j]:
                asdf(x,y,n//3)
                asdf(x+n//3,y,n//3)
                asdf(x+2*n//3,y,n//3)
                asdf(x,y+n//3,n//3)
                asdf(x+n//3,y+n//3,n//3)
                asdf(x+2*n//3,y+n//3,n//3)
                asdf(x,y+2*n//3,n//3)
                asdf(x+n//3,y+2*n//3,n//3)
                asdf(x+2*n//3,y+2*n//3,n//3)
                return
    if sameNum == -1:
        a +=1
    elif sameNum == 0:
        b +=1
    else:
        c +=1
        
asdf(0,0,n)
print(a, b, c, end=" ")

💡피드백

반복문을 통해 종이를 확인한다. 이전의 종이의 수가 현재 종이의 수가 다르다면 3*3 범위를 재귀적으로 탐색한다.

매개변수는 탐색 할 종이의 왼쪽 위 좌표와 해당 종이의 크기를 넣어준다.

❗️ 나는 9개의 함수를 탐색했지만 아래와 같이 for문을 통해 탐색 가능하다.

# 3*3 범위를 재귀하는 방법

# 3 * 3 범위를 재귀적으로 탐색
                for k in range(3):
                    for l in range(3):
                        dfs(x + k * z // 3, y + l * z // 3, z // 3)