[BOJ] #2630 색종이 만들기 (Python)

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

🚀

알고리즘 분류 🔗

분할정복, 재귀

🚀

문제 설명 🔗

정사각형의 종이를 N x N 크기로 자릅니다. 이 종이는 파란색, 하얀색으로 색칠되어 있습니다.

이 종이를 잘라서 한 색으로 이루어진 정사각형의 색종이를 만들려고 합니다.

색종이를 잘라서 만들 수 있는 색종이의 개수를 구하면 됩니다.

✅

입력 🔗

첫째 줄에 N이 주어집니다. (1 ≤ N ≤ 128)

아래로 N줄에 걸쳐 색종이의 색깔이 주어집니다.

각 줄은 N개의 0 또는 1로 이루어져 있습니다.

0은 하얀색, 1은 파란색을 의미합니다.

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

✅

출력 🔗

첫째 줄에 하얀색 색종이의 개수, 둘째 줄에 파란색 색종이의 개수를 출력합니다.

9
7

🚀

풀이 🔗

입력받은 색종이를 2차원 리스트에 저장합니다.
색종이를 4등분하여 재귀적으로 검사합니다.
각 색종이가 모두 같은 색인지 확인합니다.
모두 같은 색이면 해당 색의 개수를 증가시킵니다.
모두 같은 색이 아니면 4등분하여 다시 검사합니다.
최종적으로 하얀색과 파란색의 개수를 출력합니다.

🚀

코드 - Python 🔗

 # 입력 처리
N = int(input())
colors = [list(map(int, input().split())) for _ in range(N)]
 
 # 정답 저장: answer[0] = 흰색 개수, answer[1] = 파란색 개수
answer = [0, 0]
 
 
def count_color(x, y, size):
    """
    (x, y)를 시작으로 size x size 정사각형을 검사한다.
    만약 모든 색이 같다면 색종이 개수 증가,
    아니면 4등분하여 재귀 처리.
    """
    color = colors[x][y]
    all_same = True
 
    # 해당 영역 전체가 같은 색인지 확인
    for i in range(x, x + size):
        for j in range(y, y + size):
            if colors[i][j] != color:
                all_same = False
                break
        if not all_same:
            break
 
    if all_same: # 모두 같은 색이면 해당 색의 개수 증가
        answer[color] += 1
    else:
        # 4등분하여 재귀 호출
        half = size // 2
        count_color(x, y, half)                 # 왼쪽 위
        count_color(x, y + half, half)          # 오른쪽 위
        count_color(x + half, y, half)          # 왼쪽 아래
        count_color(x + half, y + half, half)   # 오른쪽 아래
 
 
 # 시작 좌표 (0, 0), 전체 크기 N
count_color(0, 0, N)
 
 # 출력
print(answer[0])  # 하얀색 색종이 개수
print(answer[1])  # 파란색 색종이 개수

🚀

핵심 🔗

입력으로 NxN 정사각형 종이가 주어짐 (N은 2의 거듭제곱).
각 칸은 0(흰색) 또는 1(파란색).
모든 칸이 같은 색이 아닐 경우, 정사각형을 4등분해서 재귀적으로 처리.
더 이상 나눌 수 없을 때까지 반복해서
색종이 개수(= 단색 블록 개수)
를 세는 문제.

✅

시간 복잡도 🔗

한 번 검사할 때 영역을 모두 순회: 최대 NxN = 128x128 = 16,384칸
모든 칸을 한 번씩만 검사하게 됨
최악의 경우: 색이 전부 다 달라서 계속 분할됨 → 재귀 깊이 최대 log₂N

최종 시간복잡도: O(N²)

🚀

반례 모음(예제 제외) 🔗

차례로 하얀색, 파란색 종이 색

answer: 1 0

2
0 0
0 0

answer: 0 1

2
1 1
1 1

answer: 2 2

2
0 1
1 0

answer: 3 1

2
0 1
0 0

answer: 8 8