[백준/파이썬] 1780번: 종이의 개수

문제

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

풀이

• N×N크기의 종이
  • 각 칸은 -1, 0, 1
• 종이가 모두 같은 수라면 pass
• 아니라면 9등분
• -1 개수, 0 개수, 1 개수

분할 정복을 활용한 문제
색종이 만들기 문제에서 4등분이 아닌 9등분 하는 것이나 마찬가지

쿼드트리에서 풀어본 것처럼 문제를 한 번 풀어보겠습니다.

(편의상 -1은 2로 작성하였습니다..)
위와 같은 배열이 주어졌습니다.
모든 값이 같지 않으므로 각 영역의 값이 모두 같아질 때까지 분할을 해보겠습니다.

이제 모든 영역의 값이 같은 값으로만 구성되었죠?
값이 올바른지 검사를 해보겠습니다.

-1은 10개

0은 12개

1은 11개

값이 일치하네요 👍

이제 이를 바탕으로 코드를 작성하겠습니다.

def func(x, y, n): # 시작 인덱스 (x,y), 배열의 길이 n
    tmp = arr[x][y] # 현재 위치
    for i in range(x, x+n): # 시작 인덱스부터 n까지
        for j in range(y, y+n):

시작 인덱스와 배열의 길이를 매개변수로 입력 받아 옵니다.
이를 바탕으로 검사를 시작 해볼게요.

            if tmp != arr[i][j]: # 현재 위치한 값과 일치하지 않을 경우
                idx = n // 3
                for a in range(3):
                    for b in range(3):
                        func(x+idx*a, y+idx*b, idx) # 9분할하여 재귀
                return
    res.append(tmp)

현재 위치의 값과 검사하고 있는 배열의 값이 다를 경우 재귀를 합니다.
편의를 위해 idx를 선언하고 재귀하려는 함수를 하나하나 선언하면 9줄이나 되므로 for문을 이용해줍니다.
재귀가 끝나면 return을 해준 후 결과 배열에 tmp 값을 추가해줍니다.
(return을 하지 않으면 쓸 데 없는 값까지 결과 배열에 추가되므로 주의 ⚠️)

코드

import sys
input = sys.stdin.readline

def func(x, y, n):
    tmp = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if tmp != arr[i][j]:
                idx = n // 3
                for a in range(3):
                    for b in range(3):
                        func(x+idx*a, y+idx*b, idx)
                return
    res.append(tmp)

if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    res = []

    func(0,0,n)
    print(res.count(-1), res.count(0), res.count(1), sep='\n')