BOJ2630 색종이 만들기

문제

BOJ2630 색종이 만들기
실버III | 백준 2630 | Python3 파이썬 풀이

알고리즘

BOJ1780 종이의 개수문제와 매우 유사하다. (BOJ1780 종이의 개수 - 풀이)

이 문제는 문제에 설명이 아주 자세하게 쓰여있어서 그대로 따라 구현하면 된다.

이런 종이의 경우

위 사진과 같이 나누면 된다.

각 종이를 4등분 해나가며 그 그룹이 같은 값(1 또는 0)으로 이루어져있다면 더 이상 나누지 않아도 된다.

파이썬의 2차원 리스트 슬라이싱을 이용해 나눠진 4개의 정사각형 그룹으로 재귀함수를 호출한다.

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

코드

import sys

input = sys.stdin.readline

blue = 0  # 1 갸수
white = 0 # 0 개수

# 파란색(1)의 개수를 세는 함수
def count_blue(part, c):
    count = 0
    for i in range(c):
        for j in range(c):
            if part[i][j] == 1:
                count += 1

    return count


def check(part, c):
    global blue, white
    # 1x1 크기라면
    if c == 1:
        if part[0][0] == 1:
            blue += 1
        else:
            white += 1
        return
	
    # 전부 파란색(1)이라면
    if count_blue(part, c) == c * c:
        blue += 1
        return
    # 전부 흰색(0)이라면
    elif count_blue(part, c) == 0:
        white += 1
        return
    
    # 정사각형 4개 그룹으로 나누어 재귀 호출
    else:
        check([row[:c//2] for row in part[:c//2]], c//2)
        check([row[:c//2] for row in part[c//2:]], c//2)
        check([row[c//2:] for row in part[:c//2]], c//2)
        check([row[c//2:] for row in part[c//2:]], c//2)
    

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

check(p, N)

print(white)
print(blue)

결과