[백준 1780 파이썬] 종이의 개수 (실버2, 분할 정복)

알고리즘 유형 : 분할 정복
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

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

def split9(x, y, size):
    x1 = x + size
    x2 = x1 + size
    y1 = y + size
    y2 = y1 + size
    yield x, y
    yield x, y1
    yield x, y2
    yield x1, y
    yield x1, y1
    yield x1, y2
    yield x2, y
    yield x2, y1
    yield x2, y2

def slicing(x, y, size):
    if size == 1:
        return (0, 0, 1) if paper[x][y] == 1 else (0, 1, 0) if paper[x][y] == 0 else (1, 0, 0)
    
    check = paper[x][y]
    isFull = True
    for i in range(x, x+size):
        for j in range(y, y+size):
            if check != paper[i][j]:
                isFull = False
                break

    if isFull:
        return (0, 0, 1) if check == 1 else (0, 1, 0) if check == 0 else (1, 0, 0)
    else:
        minus, zero, plus = 0, 0, 0
        for u, v in split9(x, y, size//3):
            m, z, p = slicing(u, v, size//3)
            minus += m
            zero += z
            plus += p
        return minus, zero, plus

print(*slicing(0, 0, N), sep = "\n")

풀이 요약

1. 2630, 1992 문제랑 풀이가 똑같다. 차이점은 9분할이고, 반환 형태가 3인자 또는 길이 3의 튜플이다.

2. 9분할 제너레이터로 for를 돌면서 각 분할 종이마다 -1, 0, 1 그룹의 개수를 다 수합한 후, 수합한 minus, zero, plus 변수 다인자 반환.

3. for 진입 전에 한번, 현재 재귀 프로세스의 size에 해당하는 종이가 전체 -1, 0 또는 1인 경우를 미리 걸러줘서 재귀 깊이 & 횟수 줄이기

배운 점, 어려웠던 점

• 저번에 푼 문제랑 풀이가 똑같아서 수월했다. 구현력(풀이 속도)을 숙련할 수 있었다.