[백준] 1780번 파이썬

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

문제 해결 방법

1. 분할 탐색 문제로, 매단계마다 9개의 구역으로 나눠 탐색하면 된다.
2. 문제가 어렵지 않기 때문에, 직접 예제를 그려보고, travel 함수내의 범위를 나눠 9개의 구역으로 탐색하는 범위를 체크하면 금방 해결 할 수 있다.
3. 비슷한 문제로는 1992번 쿼드트리, 2630번 종이접기가 있다.

import sys
input = sys.stdin.readline

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


# 1사분면 ~ 9사분면 분할 탐색
def travel(x, y, N):
    check = PAPER[x][y]
    for row in range(x, x+N):
        for col in range(y, y+N):
            if check != PAPER[row][col]:
                # 1사분면
                travel(x, y, N // 3)
                # 2사분면
                travel(x, y + N // 3, N // 3)
                # 3사분면
                travel(x, y + 2 * (N // 3), N // 3)
                # 4사분면
                travel(x + N // 3, y, N // 3)
                # 5사분면
                travel(x + N // 3, y + N // 3, N // 3)
                # 6사분면
                travel(x + N // 3, y + 2 * (N // 3), N // 3)
                # 7시분면
                travel(x + 2 * (N // 3), y, N // 3)
                # 8사분면
                travel(x + 2 * (N // 3), y + N // 3, N // 3)
                # 9사분면
                travel(x + 2 * (N // 3), y + 2 * (N // 3), N // 3)
                return None

    if check == -1:
        answer[0] += 1
    elif check == 0:
        answer[1] += 1
    else:
        answer[2] += 1

    return None


travel(0, 0, N)
for i in range(3):
    print(answer[i])