코드

# 전체 종이의 한 변의 길이 (2, 4, 8, 16, 32, 64, 128)
N = int(input())

# 색종이 색상 정보를 입력받을 리스트
paper = [list(map(int, input().split())) for _ in range(N)]

# 색 종류 (0 : 흰색, 1 : 파란색)
color_list = []

# 쿼드트리 알고리즘
def quad_tree(x, y, N):
    
    # x, y 좌표의 현재 색을 담을 변수 (0 or 1)
    color = paper[x][y]
    
    # 모든 좌표를 탐색
    for i in range(x, x+N):
        for j in range(y, y+N):
            
            # 탐색이 시작된 좌표의 색과 현재 탐색 중인 좌표의 색이 다르면
            # 4분할을 하여 재탐색 
            # x, y => 분할된 영역의 좌측 맨 위 좌표
            # N => 4분할이기 때문에 길이는 절반
            if color != paper[i][j]:
                quad_tree(x, y, N//2)
                quad_tree(x, y+N//2, N//2)
                quad_tree(x+N//2, y, N//2)
                quad_tree(x+N//2, y+N//2, N//2)
                return
    if color == 0:
        color_list.append(0)
    else:
        color_list.append(1)
        
# (0, 0)부터 시작
quad_tree(0, 0, N)

# 흰색의 개수
print(color_list.count(0))

# 파란색의 개수
print(color_list.count(1))

문제 해설

분할 정복, (쿼드 트리, 재귀)를 활용한 문제이다.

백준 1992 - 쿼드 트리

위의 문제와 매우 유사하여 풀이는 위의 링크를 참고해주시기 바랍니다!!!

참고 블로그

댓글남기기

참고