[알고리즘] 분할정복 - 백준 1780번 종이의 개수

import sys
N = int(sys.stdin.readline())
papers = [list(map(int, input().split())) for _ in range(N)]
minus_paper, zero_paper, one_paper = 0, 0, 0

def solution(x, y, n):
    global minus_paper, zero_paper, one_paper
    color = papers[x][y]

    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != papers[i][j]:
                solution(x, y, n//3)
                solution(x+n//3, y, n//3)
                solution(x+(n//3)*2, y, n//3)
                solution(x, y+n//3, n//3)
                solution(x+n//3, y+n//3, n//3)
                solution(x+(n//3)*2, y+n//3, n//3)
                solution(x, y+(n//3)*2, n//3)
                solution(x+n//3, y+(n//3)*2, n//3)
                solution(x+(n//3)*2, y+(n//3)*2, n//3)
                return
    if color == -1:
        minus_paper += 1
    elif color == 0:
        zero_paper += 1
    else:
        one_paper += 1


solution(0, 0, N)
print(minus_paper)
print(zero_paper)
print(one_paper)

풀이과정

1. 종이를 2차원 배열로 받는다. input() 대신 sys.stdin.readline() 을 사용하면 효율성이 더 좋다.
2. 구해야 할 종이는 global로 받아야한다.
3. 첫번째 위치의 색종이 색깔을 color에 담는다.
4. 나눠진 부분의 이중 for문을 돌면서 하나라도 color와 같지 않다면 재귀를 이용하여 (구)사분면으로 나눈다.
5. 모든 색이 같은 경우, 종이의 개수를 구한다.

* '색종이 만들기' 문제와 매우 비슷하다.

https://velog.io/@minidoo/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5-%EB%B0%B1%EC%A4%80-2630%EB%B2%88-%EC%83%89%EC%A2%85%EC%9D%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0