[알고리즘] 백준 2630번 - 재귀함수 문제풀이

백준 2630 번 문제는 색종이 접기 문제인데.... 진짜 이해를 초반에 못했다.

아래에는 주석을 달아둔 코드이므로 참고하자.

def count_paper(x, y, n, paper):
    """
    주어진 정사각형 종이에서 (x, y) 위치부터 시작해서
    n 크기의 정사각형을 검사하여 같은 색인 색종이의 개수를 반환하는 함수.
    """
    if n == 1: # 종이의 크기가 1x1이면 해당 위치의 색종이 1개 반환
        return [0, 1] if paper[x][y] else [1, 0]
​
    # 해당 정사각형의 색이 모두 같은지 확인
    same_color = True
    for i in range(x, x+n):
        for j in range(y, y+n):
            if paper[i][j] != paper[x][y]:
                same_color = False
                break
        if not same_color:
            break
​
    # 모두 같은 색인 경우 해당 색종이 수 반환
    if same_color:
        return [0, 1] if paper[x][y] else [1, 0]
​
    # 4등분하여 재귀적으로 색종이 수 계산
    size = n//2
    counts = [0, 0] # 하얀색, 파란색 색종이 수를 저장할 리스트
    for i in range(2):
        for j in range(2):
            result = count_paper(x+i*size, y+j*size, size, paper)
            counts[0] += result[0] # 하얀색 색종이 수 합산
            counts[1] += result[1] # 파란색 색종이 수 합산
​
    return counts
​
# 입력 받기
n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
​
# 색종이 수 계산
result = count_paper(0, 0, n, paper)
​
# 결과 출력
print(result[0])
print(result[1])