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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1780번 종이의 개수
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

-1, 0, 1로 채워진 N x N 종이를 같은 값으로만 이루어진 정사각형 단위로 분할했을 때 각 값 종이 개수를 구하는 문제입니다.

코드

import sys;read=sys.stdin.readline

n=int(read())
a,l=[0,0,0],[list(map(int,read().split()))for _ in range(n)]

def div(si,ei,sj,ej):
    global a,l
    f=False
    for i in range(si,ei):
        for j in range(sj,ej):
            if l[i][j]!=l[si][sj]:
                f=True
                break
        if f:break
    if f:
        for i in range(3):
            for j in range(3):
                ti,tj=si+(ei-si)//3*i,sj+(ej-sj)//3*j
                div(ti,ti+(ei-si)//3,tj,tj+(ej-sj)//3)
    else:a[l[si][sj]+1]+=1

div(0,n,0,n)
print(*a,sep='\n')

설명

현재 영역이 모두 같은 값인지 검사하고, 다르면 3x3으로 다시 분할해 재귀 호출합니다.

같은 값이면 해당 카운터(-1,0,1 -> 인덱스 0,1,2)를 증가시킵니다.

---

• 백준 문제풀이 전체 목록 보기

---