boj2630 - 색종이 만들기

문제

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

내 코드 (100ms)

import sys

def paper_sum(paper):
    n = len(paper)
    tot = 0
    for i in range(n):
        tot += sum(paper[i])
    return tot

def dq(paper, n):
    global blue, white
    # print(f'front dq blue: {blue}, white: {white}')

    if paper_sum(paper) == n*n:
        blue += 1
        return
    if paper_sum(paper) == 0:
        white += 1
        return
    
    nn = n//2
    total1, total2, total3, total4 = [], [], [], []
    for i in range(nn): # 위에 두 조각의 각 합
        total1.append(paper[i][:nn])
        total2.append(paper[i][nn:n])
    for i in range(nn,n): # 아래 두조각 합
        total3.append(paper[i][:nn])
        total4.append(paper[i][nn:n])
    # print(total1, total2, total3, total4)
    dq(total1, nn)
    dq(total2, nn)
    dq(total3, nn)
    dq(total4, nn)
    return
    


if __name__ == '__main__':
    input = sys.stdin.readline

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

    white , blue = 0, 0
    dq(paper, N)
    print(white)
    print(blue)

색종이 각 원소가 모두 같은 색이 아닐 경우
2차원 리스트를 4등분으로 쪼개어 다시 2차원리스트로 만들고, dq함수 호출하는 방식

시간 더 적게 걸리는 코드 (80ms)

import sys
input = sys.stdin.readline

N = int(input())

paper = []
for i in range(N):
    tmp = list(map(int,input().strip().split()))
    paper.append(tmp)

blue = 0
white = 0
def quadtree(x,y,n):
    global blue, white
    check = paper[x][y]
    for i in range(x,x+n):
        for j in range(y, y+n):
            if check != paper[i][j]:
                quadtree(x,y,n//2)
                quadtree(x,y+n//2,n//2)
                quadtree(x+n//2,y,n//2)
                quadtree(x+n//2,y+n//2,n//2)
                return
    if check == 0:
        white+=1
        return
    else:
        blue+=1
        return

quadtree(0,0,N)
print(white)
print(blue)

색종이 각 원소가 모두 같은 색인지 확인 : 각 종이의 (0,0)원소를 check으로 두고 for 문 돌면서 모든 원소가 check과 같은지 확인

색이 다를 때 재귀 호출 : 리스트 또 만들필요 없이 체크할 시작 원소 좌표롸 색종이 크기만 반으로 나누어서 호출