[Solved] BOJ: 2630 | 색종이 만들기

문제

가로 N/2 세로 N/2씩 잘라서 1이나 0으로만 이루어진 정사각형 만들기

입력과 출력

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

---

문제 해결 요약

1. 색종이 전체를 순회하면서 왼쪽상단(맨 처음 인덱스)와 값이 같은지 확인
2. 다르다면 가로 세로 길이를 반으로 잘라 4등분 하고, 4개의 색종이에 대해 다시 1 진행 -> 재귀

코드 설명

import 및 입력받기

-

import sys
input = sys.stdin.readline

def solutions(N):
    t = []
    for _ in range(N):
        t.append(list(map(int, input().split())))

    blue, white = cut(0, 0, 0, 0, N, t)
    return f'{white}\n{blue}'

n = int(input())
print(solutions(n))

• 색종이 너비, 높이의 길이 n을 입력 받음
• t에 색종이 맵을 입력받음
• blue 색종이와 white 색종이 개수를 리턴하는 cut함수 실행
• 파라미터 초기값 설정: y, x 좌표 (0,0), blue white 색종이 개수 (0, 0), 색종이 너비높이 길이 N, 색종이 맵 t

재귀 함수

분할된 각 색종이들을 순회하면서 재귀

-

start = total[y][x]

• start로 맨 처음 인덱스 받기

if L == 1: # 크기가 1*1 일 때
        if start == 1:
            return B+1, W
        else:
            return B, W+1

• 색종이 너비 길이가 1이라면 blue, white 색종이 개수 갱신해서 리턴

cutting = False

• 잘라야하는지 여부를 판단하는 cutting 변수 정의 및 초기값 False

for i in range(y, y+L):
        for j in range(x, x+L):
            if total[i][j] != start: # 전체가 한 색깔X -> 자르기
                cutting = True

• 한 색종이의 맨 처음 인덱스부터 순회하면서 맨 처음 인덱스의 값과 다르다면 잘라야 하는 종이 -> cutting = True

if cutting:
        for dy, dx in zip([0, 1, 0, 1], [0, 0, 1, 1]):
            B, W = cut(y+L//2*dx, x+L//2*dy, B, W, L//2, total)

• if cutting = True: 분할된 네 개의 색종이에 대해 cut함수 실행 -> 재귀

else:
        if start == 1: # 전체가 한 색깔일 때
            return B+1, W
        else:
            return B, W+1

• if cutting = False: 한 색종이의 첫 번째 인덱스의 값이 곧 색종이의 색깔을 결정 -> 색종이 개수 갱신 및 리턴

def cut(y, x, B, W, L, total):
    start = total[y][x]
    if L == 1: # 크기가 1*1 일 때
        if start == 1:
            return B+1, W
        else:
            return B, W+1

    cutting = False
    for i in range(y, y+L):
        for j in range(x, x+L):
            if total[i][j] != start: # 전체가 한 색깔X -> 자르기
                cutting = True

    if cutting:
        for dy, dx in zip([0, 1, 0, 1], [0, 0, 1, 1]):
            B, W = cut(y+L//2*dx, x+L//2*dy, B, W, L//2, total)
    else:
        if start == 1: # 전체가 한 색깔일 때
            return B+1, W
        else:
            return B, W+1
    return B, W

• cut 함수 전체

---

전체 코드

import sys
input = sys.stdin.readline

def cut(y, x, B, W, L, total):
    start = total[y][x]
    if L == 1: # 크기가 1*1 일 때
        if start == 1:
            return B+1, W
        else:
            return B, W+1

    cutting = False
    for i in range(y, y+L):
        for j in range(x, x+L):
            if total[i][j] != start: # 전체가 한 색깔X -> 자르기
                cutting = True

    if cutting:
        for dy, dx in zip([0, 1, 0, 1], [0, 0, 1, 1]):
            B, W = cut(y+L//2*dx, x+L//2*dy, B, W, L//2, total)
    else:
        if start == 1: # 전체가 한 색깔일 때
            return B+1, W
        else:
            return B, W+1
    return B, W

def solutions(N):
    t = []
    for _ in range(N):
        t.append(list(map(int, input().split())))

    blue, white = cut(0, 0, 0, 0, N, t)
    return f'{white}\n{blue}'

n = int(input())
print(solutions(n))