백준 2630번 - 색종이 만들기

파란색 사각형과 하얀색 사각형의 개수를 구하는 문제이다. 1/4로 계속해서 나누어 주면서 만약 나누어진 영역의 값이 모두 1이거나 모두 0 이면 카운트해주면 되겠다.

 

2차원 배열로 입력값을 받기 때문에 분할을 한 뒤 각 영역의 시작과 끝 인덱스가 중요할 것이다. merge sort 알고리즘을 짜 보면 대충 어떻게 풀 지 감이 온다. merge sort에서는 left와 right로 mid를 구해서 left부터 mid, mid+1부터 right까지 두 개로 분할해서 재귀 함수를 만들었다. 같은 원리로 이 문제에서는 두 개로 나누는 것이 아니라 네 개로 나눌 뿐이다. 그렇다면 어떻게 나누어야 할까?

 

시작 부분의 인덱스와 끝 부분의 인덱스를 안다면 그것을 꼭짓점으로 하는 사각형을 구할 수 있을 것이고, 모두 1인지 혹은 0인지 판별한 뒤, 모두 1이거나 0이면 그에 따른 결괏값을 카운트하면 된다. 중요한 것은 4개의 작은 사각형들로 나누어질 때 인덱스를 구하는 것이다. 시작 부분의 인덱스를 left1, left2라고 하고 끝 부분의 인덱스를 right1, right2라고 하자.

나누는 기준이 중앙값이기 때문에, mid1 = (left1 + right1), mid2 = (left2 + right2)로 설정할 수 있다. 나누어지는 사각형의 시작과 끝 인덱스를 left1, left2, right1, right2, mid1, mid2를 이용하여 설정하여 재귀 함수를 만들면 된다.

 

##함수 선언 부분
def get_paper(square, left1, left2, right1, right2, answer):
    is_one = 1
    is_zero = 1
    for i in range(left1, right1+1): #범위 안의 사각형이 모두 1인가 확인
        for j in range(left2, right2+1):
            if square[i][j] == 1:
                is_one = 1
            else:
                is_one = 0
                break
        if not is_one:
            break
    if is_one:
        answer[1] += 1
        return

    for i in range(left1, right1+1): #범위 안의 사각형이 모두 0인가 확인
        for j in range(left2, right2+1):
            if square[i][j] == 0:
                is_zero = 1
            else:
                is_zero = 0
                break
        if not is_zero:
            break
    if is_zero:
        answer[0] += 1
        return

    if left1 < right1 and left2 < right2 : #
        mid1 = (left1 + right1)//2
        mid2 = (left2 + right2)//2
        get_paper(square,left1,left2,mid1,mid2,answer)
        get_paper(square, left1, mid2+1, mid1, right2, answer)
        get_paper(square, mid1+1, left2, right1, mid2, answer)
        get_paper(square, mid1+1, mid2+1, right1, right2, answer)
##변수 선언 부분
square = []

##메인 함수 부분
if __name__ == "__main__":
    N = int(input())
    square = [[int(x) for x in input().split()]for y in range(N)]
    answer = [0]*2
    get_paper(square, 0, 0, N-1, N-1, answer)
    print(answer[0])
    print(answer[1])

merge sort 알고리즘을 짜 보기 전에는 분할 정복이 되게 낯선 개념이었는데, 재귀 함수를 이용하여 분할을 해보니 생각보다 할만했다.