[Python] 백준/BOJ 2630번: 색종이 만들기 (Silver 2)

💻 Problem

문제 보러 가기

 
여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다.
잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.
 

✏️ Solution 1

import sys
input = sys.stdin.readline

def cut(r, c, n): # 시작점 (r, c), 한 변의 길이
    global white, blue

    total = sum(map(sum, [row[c:c + n] for row in paper[r:r + n]]))

    if total == 0:
        white += 1
    elif total == n * n:
        blue += 1
    else:
        # 종이 크기가 한 칸이면 종료한다
        if n == 1:
            return
        # 종이를 자른다
        n //= 2
        cut(r, c, n) # 왼쪽 위
        cut(r, c + n, n) # 오른쪽 위
        cut(r + n, c, n) # 왼쪽 아래
        cut(r + n, c + n, n) # 오른쪽 아래


n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
white, blue = 0, 0 # 흰색 종이 개수, 파란색 종이 개수

cut(0, 0, n)
print(white)
print(blue)

한 변의 길이가 n일 때, 정사각형 모든 칸의 숫자를 다 더 더한 값이 0이면 흰색 종이, n * n이면 파란색 종이, 그 외의 숫자면 더 자르는 방식이다.
이 방식을 떠올리고 흰색 종이인지 파란색 종이인지 판별하는 아이디어가 한 칸씩 살펴보는 것보다 좋다고 생각했었는데..
다른 사람들보다 시간이 오래 걸리기에 다시 확인해보니 바보였넹

total을 구하는 연산보다 그냥 하나씩 검사하는 게 빠르자낭,,
 

✏️ Solution 2

import sys
input = sys.stdin.readline

def cut(r, c, n): # 시작점 (r, c), 한 변의 길이
    global white, blue

    color = paper[r][c]

    for i in range(r, r + n):
        for j in range(c, c + n):
            # 다른 색인 칸이 있으면 종이를 자른다
            if color != paper[i][j]:
                n //= 2
                cut(r, c, n) # 왼쪽 위
                cut(r, c + n, n) # 오른쪽 위
                cut(r + n, c, n) # 왼쪽 아래
                cut(r + n, c + n, n) # 오른쪽 아래
                return

    if color == 0:
        white += 1
    elif color == 1:
        blue += 1

n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
white, blue = 0, 0 # 흰색 종이 개수, 파란색 종이 개수

cut(0, 0, n)
print(white)
print(blue)