[백준 1780] 종이의 개수 (Python)

2022. 8. 22. 10:24

문제 링크 #

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

문제 해설 #

Idea #

Divide and Conquer
2차원 배열의 요소를 완전탐색하면서 동일한 값으로 구성되지 않을 경우,
행렬을 9등분하여 재귀적 호출 수행
처음 시도에서는 행렬을 매번 슬라이싱하면서 전달하여 시간 초과가 발생
행렬의 시작 인덱스 번호를 전달하고 길이만큼 참조하는 방식으로 시간 복잡도 개선

Data Size #

N: 1 <= int <= 3^7

해설 코드 #

python

import sys
input = sys.stdin.readline

value2id = {-1:0,0:1,1:2}

# ============== 1안 (시간초과) =============

from itertools import chain
mat_slice = lambda mat,r1,r2,c1,c2: list(map(lambda x: x[c1:c2], mat[r1:r2]))

def nona_comp(n, arr, answer):
    values = set(chain.from_iterable(arr))
    if len(values) == 1:
        answer[value2id[values.pop()]] += 1
        return
    div = n//3
    for i in range(3):
        for j in range(3):
            nona_comp(div, mat_slice(arr,div*i,div*(i+1),div*j,div*(j+1)), answer)

# =============== 2안 (통과) ===============

def nona_comp(n, arr, r, c, answer):
    start = arr[r][c]
    for row in range(r,r+n):
        for col in range(c,c+n):
            if arr[row][col] != start:
                div = n//3
                for i in range(3):
                    for j in range(3):
                        nona_comp(div, arr, r+div*i, c+div*j, answer)
                return
    answer[value2id[start]] += 1

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

for num in answer:
    print(num)