백준 1780 종이의 개수

종이의 개수 (백준 1780)

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

쿼드 트리의 응용 문제이다
num이 3의 배수로 주어지기에
주어진 행렬을 3x3으로 나누어 나가면서
재귀를 돌리는 방식으로 풀었다

각각의 블록(length로 나누어진)에서
같은 로직을 구함으로서 값을 얻을 수 있기에
‘분할정복’에 해당한다

(서로의 값에 종속성이 없기에, 다른 하위 문제를 풀어도 현재 하위문제와는
연관이 없기에 ‘DP’로는 풀 수 없고, 지역적 최적해를 구할만한 특정한 조건이 없다고
생각하였기에 greedy를 적용시킬 수는 없다고 생각하였다)

Code

import sys

sys.setrecursionlimit(10**8)

inp = sys.stdin.readline

num = int(inp().strip())

graphs = [list(map(int,inp().split())) for _ in range(num)]

answer = [0 for _ in range(3)] # -1, 0, 1 갯수

def dq(startX,startY,length):
    if (startX < 0 or startX >= num or
        startY <0 or startY >= num):
        return
    
    startSymbol = graphs[startX][startY]

    sameSymbol = True
    for i in range(startX,startX + length):
        for j in range(startY,startY + length):
            if graphs[i][j] != startSymbol:
                sameSymbol = False
                break
        if sameSymbol == False:
            break
    
    if sameSymbol == True:
        answer[startSymbol + 1] +=1 # 어차피 -1,0,1 이므로 그냥 +1 해준 인덱스에 더해주면 된다
    else:
        nextLength = int(length / 3)
        for i in range(3):
            for j in range(3):
                dq(startX + nextLength * i,startY + nextLength * j,nextLength)

dq(0,0,num)

for i in answer:
    print(i)

해결 아이디어

1. 처음 시작한 종이가 정해진 길이(length)만큼 2중 for문을 돌았을 때,
   자신과 다른 종이가 있다면 break한다
2. bool 변수를 통하여 해당 내용을 체크하고
   전부 같다면 해당 종이의 개수를 + 1
   아니면 9개로 나누어 재귀를 돌린다