[백준] 2630번: 색종이 만들기

문제 링크

---

아이디어

큰 부분에서 작은 부분으로 나누어 가며 문제를 작게 만든다. 재귀함수를 이용하였다.

해설

주석으로 설명 대체

코드

import sys

def getPaperNum(paper, row, col, size):
    '''
    큰 종이부터 점점 작은 종이로 나눠가며 종이의 개수를 구하는 함수

    return : 나뉜 하얀 종이 수, 나뉜 파란 종이 수
    '''
    isGroup = True
    group = paper[row][col]
    # 모든 점을 순회하면서 같은 색인지 체크
    for dRow in range(size):
        for dCol in range(size):
            if paper[row + dRow][col + dCol] != group:
                isGroup = False
                break
        if not isGroup:
            break
    # 같은 그룹이면 함수 종료
    if isGroup:
        if group == 0:
            return (1, 0)
        elif group == 1:
            return (0, 1)
    # 같은 그룹이 아니면 종이를 네 개로 나누어 재귀함수 호출
    else :
        newSize = size // 2
        paperNum = [0, 0]
        for dRow, dCol in [(0, 0), (newSize, 0), (0, newSize), (newSize, newSize)]:
            paperNumOfDividedPaper = getPaperNum(paper, row + dRow, col + dCol, newSize)
            paperNum[0] += paperNumOfDividedPaper[0]
            paperNum[1] += paperNumOfDividedPaper[1]
        return tuple(paperNum)

n = int(sys.stdin.readline().rstrip())
paper = []
for _ in range(n):
    paper.append(list(map(int, sys.stdin.readline().rstrip().split())))

paperNum = getPaperNum(paper, 0, 0, n)
print(paperNum[0])
print(paperNum[1])