[백준 BOJ_1780] 종이의 개수 Python 풀이

출처: 백준 온라인 저지

문제

풀이

우선 영상의 크기 n과 시작하는 좌표 (y, x), 그리고 각각의 종이의 개수를 세주는 list인 cnt를 받는 nonatree함수를 만들어 주었습니다. cnt[0]에는 -1 종이의 개수를, cnt[1]에는 0 종이의 개수를, cnt[2]에는 1의 개수를 넣어주었기 때문에 cnt의 값을 바꿔줄 때는 해당 값에 +1을 한 index를 불러주면 됩니다.

n이 1일때는 제일 작은 경우(기저사례) 이기 때문에 해당 좌표 값의 개수를 증가시켜준 뒤 cnt를 반환해줍니다.

종이를 9등분하여 더이상 나눌 수 없을 때까지 재귀호출해주면 됩니다.

하지만 해당 부분이 같은 값으로 이루어져 있다면 더이상 쪼개지 않고 반환해주어야 하기 때문에 이중 for loop을 돌려 확인해주었습니다. 만약 모두 같은 값으로만 이루어져 있다면 역시 해당 좌표 값의 개수를 증가시켜준 뒤 cnt를 반환해줍니다.

n을 3으로 나누어 준 뒤, 9등분한 종이의 시작좌표 또한 나눈 n값으로 아래의 그림과 같이 바꿔줍니다.

9번의 재귀호출 뒤에는 cnt를 반환해줍니다.

코드

def nonatree(n, y, x, cnt):
    if n == 1: 
        cnt[paper[y][x]+1] += 1
        return cnt
    check = True
    for i in range(y, y+n):
        if not check:
            break
        for j in range(x, x+n):
            if paper[y][x] != paper[i][j]:
                check = False
                break
    if check:
        cnt[paper[y][x]+1] += 1
        return cnt
    new_n = n // 3
    nonatree(new_n, y, x, cnt)
    nonatree(new_n, y, x+new_n, cnt)
    nonatree(new_n, y, x+2*new_n, cnt)
    nonatree(new_n, y+new_n, x, cnt)
    nonatree(new_n, y+new_n, x+new_n, cnt)
    nonatree(new_n, y+new_n, x+2*new_n, cnt)
    nonatree(new_n, y+2*new_n, x, cnt)
    nonatree(new_n, y+2*new_n, x+new_n, cnt)
    nonatree(new_n, y+2*new_n, x+2*new_n, cnt)
    return cnt

C = int(input())
paper = [ list(map(int, input().split())) for _ in range(C)]
print(*nonatree(C, 0, 0, [0, 0, 0]), sep="\n")