[baekjoon] 1780번 : 종이의 개수 (by python 파이썬)

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

1780번: 종이의 개수

 

정답 code

#종이의 개수
n = int(input())

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

minues = 0
zero = 0
one = 0

def dfs(x,y,n):
    global minues, zero, one
    check = paper[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if paper[i][j] != check:
                for k in range(3):
                    for l in range(3):
                        dfs(x +k*n//3, y+ l*n//3, n//3)
                return
    if check == -1:
        minues += 1
    elif check == 0:
        zero += 1
    elif check == 1:
        one += 1

dfs(0,0,n)
print('{}\n{}\n{}'.format(minues,zero,one))

 

이번문제는 재귀를 활용하는 문제다

 

우선 문제를 이해하자면 틀에 들어있는 숫자가 다르면 9등분하고 계속 찾아나가는 과정이다.

 

solution

가장 중요한 dfs함수를 보자.

check함수에 종이의 첫번째 수를 담고 종이의 크기만큼 탐색해 나간다.

만약 첫번째 담긴수와 다른 수가 나왔다면 종이를 9등분한후 탐색을 시작한다.(재귀 이용)

위 과정을 반복하다 종이에 담긴 수가 모두 같다면 해당 숫자의 변수를 카운트 한다.