[Python] 백준 2630 색종이 만들기

 

문제 분석

• 정사각형
• 하얀색(0) / 파란색(1)으로 칠해져 있음
• 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양이 하얀색 또는 파란색 색종이를 만들려고 한다.
  
  
• 규칙
  • 반 씩 계속 잘라서 같은 색끼리 남거나, 더 이상 자를 수 없을 때까지
• 하얀색 색종이 / 파란색 색종이 수 출력

 

코드 설계

• 재귀로 넘겨주는 값 : 현재 배열, 배열의 시작 좌표(x, y), 배열의 크기

 

정답 코드

1차 - 실패

import sys
input = sys.stdin.readline

cnt_white = 0
cnt_blue = 0

# 한가지 색만 있는지 확인
def check_one(arr) :
    color = arr[0][0]
    if abs(color-1) in arr :
        return False
    return True

def cut(arr, x, y, n) :
    global cnt_blue # 1
    global cnt_white # 0

    if len(arr) == 1 or check_one(arr) : # 하나의 색만 있다면
        if 1 in arr :
            cnt_blue += 1
        else :
            cnt_white += 1
        return

    else : # 색이 섞여 있다면 자르기
        # # 배열을 잘라야 한다.
        # nArr = [[-1] * n for _ in range(n)]
        # for i in range(n) :
        #     for j in range(n) :
        #         nArr[i][j] = arr[x+i][y+j]

        # 4개로 자르기
        new_size = n//2
        for i in range(4):
            for j in range(4) :
                cut(arr, x+new_size*i, y+new_size*i, new_size)

n = int(input())
pArr = [list(map(int, input().split())) for _ in range(n)]

cut(pArr, 0, 0, n) # 배열, 시작 x, 시작 y, 크기
print(cnt_white)
print(cnt_blue)

 

2차 - 실패.. 어려운 재귀

import sys
input = sys.stdin.readline

cnt_white = 0
cnt_blue = 0

# 한가지 색만 있는지 확인
def check_one(arr) :
    if 1 in arr :
        color = 1
    else :
        color = 0
    if abs(color-1) in arr :
        return False
    return True

def cut(arr, x, y, n) :
    global cnt_blue, cnt_white # 0

    if n == 1 or check_one(arr) : # 하나의 색만 있다면
        if 1 in arr :
            cnt_blue += 1
        else :
            cnt_white += 1
        return

    else :
        # 4개로 자르기
        new_size = n//2
        cut(arr, x, y, new_size)  # 좌상
        cut(arr, x, y + new_size, new_size)  # 우상
        cut(arr, x + new_size, y, new_size)  # 좌하
        cut(arr, x + new_size, y + new_size, new_size)  # 우하

n = int(input())
pArr = [list(map(int, input().split())) for _ in range(n)]

cut(pArr, 0, 0, n) # 배열, 시작 x, 시작 y, 크기
print(cnt_white)
print(cnt_blue)

 

정답 코드 by chatGPT

import sys
input = sys.stdin.readline

cnt_white = 0
cnt_blue = 0

# 한 가지 색만 있는지 확인
def check_one(arr, x, y, n):
    color = arr[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if arr[i][j] != color:
                return False
    return True

def cut(arr, x, y, n):
    global cnt_blue, cnt_white

    if check_one(arr, x, y, n):  # 하나의 색만 있다면
        if arr[x][y] == 1:
            cnt_blue += 1
        else:
            cnt_white += 1
        return

    # 색이 섞여 있으면 4개로 분할
    new_size = n // 2
    cut(arr, x, y, new_size)                # 좌상
    cut(arr, x, y + new_size, new_size)      # 우상
    cut(arr, x + new_size, y, new_size)      # 좌하
    cut(arr, x + new_size, y + new_size, new_size)  # 우하

# 입력 처리
n = int(input())
pArr = [list(map(int, input().split())) for _ in range(n)]

cut(pArr, 0, 0, n)  # 배열, 시작 x, 시작 y, 크기
print(cnt_white)
print(cnt_blue)

 

 

2회차 - 25.02.17

종이를 잘라서 검사하는 것이 아니라 검사할 부분에 대한 시작 위치와 면적 보내기

 

import sys
input = sys.stdin.readline

cnt_w = 0 # 0 : 흰색
cnt_b = 0 # 1 : 파란색

def check_is_one_color(x, y, arr, side) : # x, y 종이 시작 좌표
    color = arr[x][y]
    for i in range(x, x+side) :
        for j in range(y, y+side) :
            if arr[i][j] != color:
                return False
    return True

def cut_paper(x, y, arr, side) :
    if check_is_one_color(x, y, arr, side) : # 한가지 색만 있다면
        global cnt_w, cnt_b
        if arr[x][y] == 0:
            cnt_w += 1
        else:
            cnt_b += 1
        return

    else :
        cut_n = side//2
        cut_paper(x, y, arr, cut_n)
        cut_paper(x+cut_n, y, arr, cut_n)
        cut_paper(x, y+cut_n, arr, cut_n)
        cut_paper(x+cut_n, y+cut_n, arr, cut_n)

n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
cut_paper(0, 0, paper, n)
print(cnt_w)
print(cnt_b)