💻 백준 2630: 색종이 만들기

문제 소개 🧐

주어진 N×N 크기의 색종이를 일정한 규칙에 따라 잘라, 모두 하얀색 또는 모두 파란색으로 칠해진 색종이의 개수를 세는 문제다. 종이가 모두 같은 색이 아니면 4등분하여 재귀적으로 동일한 과정을 반복한다.

입력 📝

  • 첫째 줄에 전체 종이의 한 변의 길이 N이 주어진다. (N은 2의 거듭제곱, 2 ≤ N ≤ 128)
  • 둘째 줄부터 N개의 줄에 색종이의 각 칸의 색상 정보가 주어진다. (0: 하얀색, 1: 파란색)

출력 📤

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

제한 ❌

  • 1초, 128MB

첫 번째 시도: 반복 접근을 이용한 구현 👊

Idea

주어진 종이를 가장 큰 크기(N)부터 시작하여 점차 작은 크기(N/2, N/4, …)로 나누어 가며 각 영역이 모두 같은 색인지 확인하는 반복적인 접근 방식을 사용했다.
특정 크기의 영역이 모두 같은 색이라면 해당 색종이의 개수를 세고, 해당 영역은 더 이상 탐색하지 않도록 is_made 배열을 사용하여 표시

Code

import sys
from collections import Counter

n = int(sys.stdin.readline().rstrip())
color_paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
cnt_col = [0,0]
is_made = [[False for _ in range(n)] for _ in range(n)]

def make_true(x, y, size):
    for i in range(x, x+size):
        for j in range(y, y+size):
            is_made[i][j] = True

def check_paper(x, y, size):
    color = color_paper[x][y]
    for i in range(x, x + size):
        for j in range (y, y + size):
            if color_paper[i][j] != color:
                return False
    cnt_col[color] += 1
    make_true(x, y, size)

length = n
while length > 0:
    for i in range(0, n, length):
        for j in range(0, n, length):
            if is_made[i][j]:
                continue
            if check_paper(i, j, length):
                continue
            

    length = length >> 1

print(cnt_col[0], cnt_col[1], sep='\n')

Result

  • 성공! ✅
  • is_made 배열을 활용해 이미 처리된 영역은 다시 확인하지 않도록 했다. 반복문을 통해 큰 영역부터 작은 영역까지 순차적으로 확인하며 모든 색종이의 개수를 정확하게 셀 수 있었다.

개선할 부분 🤔

  • 현재 코드는 is_made 배열을 사용해 이미 처리된 영역을 건너뛰지만, 재귀적인 분할 정복 방식을 사용하면 is_made와 같은 추가적인 방문 배열 없이도 구현할 수 있을 것 같다