[Algorithm] 백준 1780번: 종이의 개수 | 분할 정복, 전역 변수

문제 출처: https://www.acmicpc.net/problem/1780

---

1. 결과

메모리 67648KB, 시간 3592ms

2. 풀이

분할 정복을 최근에 제대로 배워보면서 분할 정복과 재귀 호출을 연습하게 되는 계기가 되었다.

또한, 나로서는 이 문제에서 하나의 함수만으로 재귀 호출 후 답을 반환하는 아이디어가 쉽게 떠오르지 않았기 때문에 전역 변수를 사용했다. 각 함수 내에서 global을 통해 counts가 전역 변수임을 알렸는데, 이런 전역 변수 선언은 가장 함수의 맨 위에서 이루어져야 한다. 파이썬은 위에서부터 순서대로 읽어나가는 경향이 있기 때문에, 함수의 중후반에서 전역 변수 선언을 했을 때는 그 이전 줄에서 이 counts라는 변수를 읽지 못하고 오류가 발생했다.

오히려 전역 변수를 나중에 선언하는 것이 유리한 상황이 있을지는 모르겠지만, 그런 방식으로도 이용할 수는 있을 것이라는 생각을 해봤다.

import sys

# 종이 정보, 열 개수(n)를 입력으로 받음.
# n == 1이거나 단일색으로 이루어진 종이일 때 [(0, 0, 0)] 형태로 반환
# 색이 다르면 9등분으로 나누고 다시 진행
counts = [0] * 3

def countPaper(paper, x, y, n):
    global counts
    pivot = paper[y][x]
    if n == 1:
        counts[pivot] += 1
        return
    tri = n // 3

    for i in range(y, y+n):
        for j in range(x, x+n):
            if pivot != paper[i][j]:
                for a in range(3):
                    for b in range(3):
                        countPaper(paper, x+tri*b, y+tri*a, tri)
                return
    counts[pivot] += 1
    return

def main():
    global counts
    N = int(sys.stdin.readline())
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    countPaper(arr, 0, 0, N)
    
    return counts

if __name__ == "__main__":
    result = main()
    print(result[-1])
    for i in result[:-1]:
        print(i)