백준 1780 - 종이의 개수

처음 든 생각

- 어제 한 쿼드트리랑 구조가 아예 똑같고 나누는 숫자만 다르네

- 0,1,-1로 다 차있는지 아닌지 비교해서 아니면 분할해서 다시 검색하는 방식으로 재귀를 구성하면 되겠다.

 

나의 답

import sys
input = sys.stdin.readline
N = int(input())

arr = [list(input().split()) for _ in range(N) ]

zero = 0
one = 0 
minus = 0

def nine_tree(x,y,n):
    global zero, one, minus

    total = 0
    start = arr[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if start != arr[i][j]:
                total = float("inf")
                break
            elif arr[i][j] == "0":
                continue
            elif arr[i][j] == "1":
                total += 1
            elif arr[i][j] == "-1":
                total -= 1
    
    if total == 0:
        zero += 1
        return
    elif total == n**2:
        one += 1
        return
    elif total == n**2 * -1:
        minus += 1
        return
    else:
        n = n//3
        nine_tree(x,y,n)
        nine_tree(x,y+n,n)
        nine_tree(x, y+ n*2,n)
        nine_tree(x+n,y,n)
        nine_tree(x+n,y+n,n)
        nine_tree(x+n,y+n*2,n)
        nine_tree(x+n*2,y,n)
        nine_tree(x+n*2,y+n,n)
        nine_tree(x+n*2,y+n*2,n)

nine_tree(0,0,N)
print(minus)
print(zero)
print(one)

 

쿼드트리와 같이 시작 좌표와 정사각형의 크기를 매개변수로 받는다.

그 다음 해당 정사각형에서 -1,0,1 셋 중에 하나로 가득차있는지 아닌지 비교한 후에 아닐 경우 9개의 정사각형으로 다시 분할해서 재귀적으로 탐색을 한다. 

 

문제 구성 자체가 이전에 풀었던 색종이 만들기, 쿼드트리와 아예 똑같아서 더 이상 풀이할 건 없을 것 같다.

 

다만 짚고 넘어가야할 점이 있다.

import sys
input = sys.stdin.readline
N = int(input())

arr = [list(input().split()) for _ in range(N) ]

zero = 0
one = 0 
minus = 0

def nine_tree(x,y,n):
    global zero, one, minus

    count_zero = 0
    count_one = 0 
    count_minus = 0
    for i in range(x,x+n):
        for j in range(y,y+n):
            if arr[i][j] == "0":
                count_zero += 1
            elif arr[i][j] == "1":
                count_one += 1
            elif arr[i][j] == "-1":
                count_minus += 1
    
    if count_zero == n**2:
        zero += 1
        return
    elif count_one == n**2:
        one += 1
        return
    elif count_minus == n**2:
        minus += 1
        return
    else:
        n = n//3
        nine_tree(x,y,n)
        nine_tree(x,y+n,n)
        nine_tree(x, y+ n*2,n)
        nine_tree(x+n,y,n)
        nine_tree(x+n,y+n,n)
        nine_tree(x+n,y+n*2,n)
        nine_tree(x+n*2,y,n)
        nine_tree(x+n*2,y+n,n)
        nine_tree(x+n*2,y+n*2,n)

nine_tree(0,0,N)
print(minus)
print(zero)
print(one)

 

처음에 풀었던 방식이었고 이렇게 풀어서 시간 초과가 떴었다. 그리고 다시 수정한 코드가 "나의 답"에 작성되어있는 코드이다.

 

-1,0,1로 다 구성되어있는지 아닌지 비교하는 로직에서 가장 큰 차이가 있다.

 

시작점을 기준으로 n^2 개 만큼의 정사각형을 탐색하는데 만약 다른 원소가 하나라도 발견되면 걔는 애초에 성립할 수 없는 정사각형이기에 뒤에 원소들을 살펴볼 필요가 없다. 하지만 처음 코드는 그럼에도 불구하고 하나씩 다 완전 탐색으로 찾는 것이기에 시간 손해가 발생할 수 없었던 코드였다.

 

재귀의 큰 구성뿐만 아니라 그 내부의 탈출 조건을 구성할 때의 시간 복잡도도 고려하여 알고리즘을 작성하는 것의 필요성을 배운 문제였다.