#1780번: 종이의 개수

문제

1780번: 종이의 개수

쿼드트리 문제와 매우 유사하지만, 요소들이 3의 배수가 된 점이 다르다. -1, 0, 1의 세 가지 값을 가지며, 종이 또한 3의 제곱수의 크기를 가진다. (1 ≤ N ≤ 3^7)

풀이

색종이 문제에서는 2의 7승 사이즈까지 1초 안에 해결했지만, 분할할 영역이 한 단계를 거칠 때 4배가 되는 거에서 9배가 되는 것으로 변경되었으므로, 시간제한 또한 1초 증가했다. 때문에 분할정복 알고리즘으로 해결이 가능하다.
가질 수 있는 값이 -1, 0, 1로 세 가지이므로, 기존에 사용했던 합을 이용하는 방식을 적용할 수 없다. 때문에 범위에 해당하는 모든 요소가 같은 값을 가지는지 검사하되, 조건에 맞지 않는 경우 빠르게 탐색을 종료하도록 했다.

num = int(input())
paper = []
for i in range(num):
    paper.append(list(map(int, input().split())))
print(paper)

ans = [0, 0, 0]
def cut(x, y, n):
    tmp = paper[x-n][y-n]
    # flag로 조건 만족 여부를 판단
    flag = True
    # 모든 요소들이 같은지 확인
    for i in range(x-n, x):
        if not flag:
            break
        for j in range(y-n, y):
            if tmp!=paper[i][j]:
                flag = False
                break
            else:
                continue
    # flag가 False인 경우, 즉 모든 요소들이 같지 않은 경우 9개 영역으로 분할
    if not flag:
        n3 = n//3
        cut(x-n3*2, y-n3*2, n3)
        cut(x-n3*2, y-n3, n3)
        cut(x-n3*2, y, n3)
        cut(x-n3, y-n3*2, n3)
        cut(x-n3, y-n3, n3)
        cut(x-n3, y, n3)
        cut(x, y-n3*2, n3)
        cut(x, y-n3, n3)
        cut(x, y, n3)
    else:
        if tmp == -1:
            ans[0] += 1
            print(x, y, -1)
        elif tmp == 0:
            ans[1] += 1
            print(x, y, 0)
        elif tmp == 1:
            ans[2] += 1
            print(x, y, 1)

cut(num, num, num)
for i in range(3):
    print(ans[i])

영역을 분할할 때 마지막 값이 아니라 시작값을 매개변수로 정한다면, 영역을 구분하는 데에 있어서 가독성이 향상될 것이다. 또한 flag를 사용하지 않고 값이 같은지 점검하는 반복분 내에 분할하는 부분을 포함시키거나, 영역을 분할하여 함수에 넣을 때 반복문을 사용하여 코드의 길이를 줄일 수 있다.