BOJ1780 종이의 개수

문제

BOJ1780 종이의 개수
실버II | 백준 1780 | Python3 파이썬 풀이

알고리즘

BOJ2630 색종이 만들기 문제와 매우 유사하다. (BOJ2630 색종이 만들기 - 풀이) 색종이 만들기는 4등분하지만, 이 문제는 9등분한다.

• 종이를 9개의 정사각형 그룹으로 나눈 뒤, 각 그룹이 모두 같은 값이라면 그 종이는 쓸 수 있는 종이이므로 그 값에 따른 개수를 기록한다.
• 만약 종이의 크기가 1x1까지 왔다면 더 이상 자를 수 없으므로 그 종이의 값에 따른 개수를 기록한다.

Python의 리스트 슬라이싱을 이용해 2차원 배열을 9개의 정사각형 그룹으로 나누어 재귀 함수를 호출한다.

check([row[:c//3] for row in part[:c//3]], c//3)
check([row[:c//3] for row in part[c//3:c//3*2]], c//3)
check([row[:c//3] for row in part[c//3*2:]], c//3)
check([row[c//3:c//3*2] for row in part[:c//3]], c//3)
check([row[c//3:c//3*2] for row in part[c//3:c//3*2]], c//3)
check([row[c//3:c//3*2] for row in part[c//3*2:]], c//3)
check([row[c//3*2:] for row in part[:c//3]], c//3)
check([row[c//3*2:] for row in part[c//3:c//3*2]], c//3)
check([row[c//3*2:] for row in part[c//3*2:]], c//3)

2차원 배열의 경우는 위와 같이 for문을 이용해 행과 열을 각각 슬라이싱해야 한다.

코드

import sys

input = sys.stdin.readline

mone = 0 # -1 그룹 개수
zero = 0 #  0 그룹 개수
pone = 0 # +1 그룹 개수

# 해당 그룹의 특정 수의 개수를 카운트하는 함수
def count(part, c, x):
    count = 0
    for i in range(c):
        for j in range(c):
            if part[i][j] == x:
                count += 1

    return count


def check(part, c):
    global pone, zero, mone
    # 만약 블록이 1x1이라면 값에 따라 카운트 증가
    if c == 1:
        if part[0][0] == 1:
            pone += 1
        elif part[0][0] == 0:
            zero += 1
        else:
            mone += 1
        return
	
    # 그 그룹의 칸이 전부 -1이라면
    if count(part, c, -1) == c * c:
        mone += 1
        return
    # 전부 0이라면
    elif count(part, c, 0) == c * c:
        zero += 1
        return
    # 전부 1이라면
    elif count(part, c, 1) == c * c:
        pone += 1
    
    # 다른 값이 섞여 있다면 9개의 정사각형 그룹으로 분할해서 체크하기
    else:
        check([row[:c//3] for row in part[:c//3]], c//3)
        check([row[:c//3] for row in part[c//3:c//3*2]], c//3)
        check([row[:c//3] for row in part[c//3*2:]], c//3)
        check([row[c//3:c//3*2] for row in part[:c//3]], c//3)
        check([row[c//3:c//3*2] for row in part[c//3:c//3*2]], c//3)
        check([row[c//3:c//3*2] for row in part[c//3*2:]], c//3)
        check([row[c//3*2:] for row in part[:c//3]], c//3)
        check([row[c//3*2:] for row in part[c//3:c//3*2]], c//3)
        check([row[c//3*2:] for row in part[c//3*2:]], c//3)


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

check(p, N)

# 각 값으로 이루어진 그룹의 개수 출력
print(mone)
print(zero)
print(pone)

결과

Python3로 제출하면 시간초과가 발생한다. Pypy3로 제출해야 한다.