코드

n = int(input())
graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))
    
# -1, 0, 1로만 채워진 종이의 개수를 담을 리스트
cnt_list = [0, 0, 0]

# 메소드 구현
def solution(x, y, n):
    color = graph[x][y]
    
    # N의 범위가 3의 7승(2187)이므로
    # 그리 크지 않음 => 4중 포문으로 시간내 구현 가능
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != graph[i][j]:
                
                # 9개의 종이로 자름 => 3*3이므로
                # 쿼드 트리와 다르게 2가 아닌 3으로 나눠줌
                # 이 때, 3으로 딸랑 한 번 나눠 주는게 아님
                # 0, 3, 6 이렇게 총 3 번 나눠줘야 하므로
                # x, y에 각각 반복문을 사용하여 분할을 구현해준다
                for k in range(3):
                    for l in range(3):
                        solution(x + k*n//3, y + l * n // 3, n//3)

                return
            
    # 위의 회귀로 실행된 반복문이 종료 된 후
    # color변수에 남은 값에 따라서 개수를 증가시켜줌
    if color == -1:
        cnt_list[0] += 1
    elif color == 0:
        cnt_list[1] += 1
    else:
        cnt_list[2] += 1
    
    return cnt_list
            
                
solution(0, 0, n)

for c in cnt_list:
    print(c)

문제 해설

분할 정복 - 쿼드 트리의 응용 문제.

쿼드 트리와 달리 9분할을 하는 문제이다. 즉 3 * 3분할 이므로 주어진 그래프를 아래 코드와 같이 3의 배수에 맞게 나누어 주면 된다.

# 9개의 종이로 자름 => 3*3이므로
                # 쿼드 트리와 다르게 2가 아닌 3으로 나눠줌
                # 이 때, 3으로 딸랑 한 번 나눠 주는게 아님
                # 0, 3, 6 이렇게 총 3 번 나눠줘야 하므로
                # x, y에 각각 반복문을 사용하여 분할을 구현해준다
                for k in range(3):
                    for l in range(3):
                        solution(x + k*n//3, y + l * n // 3, n//3)

문제에서 주어지는 n의 범위가 3의 7승으로 그리 크지 않으므로 4중 포문으로 문제를 해결하여도 시간 복잡도에 걸리지 않고 문제를 해결할 수 있다.

분할 정복의 경우 로직 자체는 익숙해지면 매우 간단한데 접할 기회가 잘 없어서 그런지 와닿지가 않는 특이한 문제이다. 백준에 있는 많은 분할 정복 문제를 풀어서 익혀야겠다.

댓글남기기

참고