[BaekJoon] 2630번: 색종이 만들기 (Python)

• Quad Tree(쿼드 트리) 라는 알고리즘 기법이 사용됐다.
  • 4분할 하여 재귀적으로 푸는 것이 이 기법이다.

Solution

import sys
from typing import List


def solution(N: int, papers_list: List[List[int]]) -> List[int]:
    answer: List[int] = []

    def quad_tree(papers_node, x, y, n):
        # 현재 영역에서의 첫번째 픽셀의 색 저장
        first_node = papers_node[y][x]

        for j in range(y, y + n):
            for i in range(x, x + n):
                # 모든 픽셀의 색이 첫 번째 픽셀과 동일한지 확인
                if papers_node[j][i] == first_node:
                    continue

                # 만약 다른 색이 하나라도 존재한다면,
                # 현재의 영역을 4개의 작은 영역으로 나누고 재귀 호출
                mid = n // 2
                quad_tree(papers_node, x, y, mid)
                quad_tree(papers_node, x, y + mid, mid)
                quad_tree(papers_node, x + mid, y, mid)
                quad_tree(papers_node, x + mid, y + mid, mid)
                return

        # 만약 모든 색이 같은 색이라면, 현재 영역의 색을 확인
        # 하얀색 개수: 0, 파란색 개수: 1
        if first_node == 0:
            answer.append(0)
            return

        answer.append(1)

    quad_tree(papers_list, 0, 0, N)

    # [하얀색 개수, 파란색 개수]
    return [answer.count(0), answer.count(1)]


N = int(sys.stdin.readline().rstrip())
papers_list: List[List[int]] = []
for _ in range(N):
    papers_list.append(list(map(int, sys.stdin.readline().rstrip().split())))

print(*solution(N, papers_list), sep='\n')

Reference

• https://www.acmicpc.net/problem/2630