[2630] 색종이 만들기 - Python

/* 문제 */
아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

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

분할 정복 문제다. 분할 정복이란 큰 문제를 작은 단위로 나눠가면서 해결한 후 합치는 방법이다.

이 문제에서는 큰 색종이를 계속해서 4개의 작은 종이로 나누는 과정을 반복한다. 나눈 종이가 한 가지 색으로만 이루어져 있다면 원하는 조건을 달성한 것이고, 그렇지 않다면 조건을 만족하지 못한 것이므로 다시 네 조각으로 나눠 확인해 본다.

 

# 정답 코드(1차)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def cut(paper, n):
    global white, blue
    half = n // 2
    # 4개로 나누기
    p1, p2, p3, p4 = [], [], [], []
    for i in range(half):
        p1.append(paper[i][:half])
        p2.append(paper[i][half:])
        p3.append(paper[half+i][:half])
        p4.append(paper[half+i][half:])

    # 각 종이가 단색인지 확인
    for p in [p1, p2, p3, p4]:
        finished = True
        first = p[0][0]
        for i in range(half):
            for j in range(half):
                if first != p[i][j]:
                    finished = False
        if finished:
            if p[0][0] == '1':
                blue += 1
            else:
                white += 1
        else:
            cut(p, half)

n = int(input())
paper= []

test = set()   
for _ in range(n):
    tem = list(input().split())
    paper.append(tem)
    test.update(tuple(tem))
    
 # 처음부터 단색인지 확인
if len(test) == 1:
    if paper[0][0] == '1':
        print(0)
        print(1)
    else:
        print(1)
        print(0)
    exit()

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

설명한 대로 cut 함수에서는 전달 받은 종이를 네 조각으로 나눈 후, 조건을 만족하는지를 판단하는 과정을 반복한다. 이 코드는 정답 판정을 받긴 했지만 코드가 길고 이미 조건을 만족하는 입력이 들어왔을 경우를 따로 체크해 줘야 한다는 불편함이 있다.

 

그래서 다음과 같이 코드를 다시 작성했다.

# 정답 코드(2차)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def cut(x, y, n):
    global paper, white, blue

    # 현재 종이가 단색인지 확인
    finished = True
    first = paper[x][y]
    for i in range(n):
        if not finished:
            break
        for j in range(n):
            if first != paper[x+i][y+j]:
                finished = False
    
    if finished:
        if paper[x][y] == '1':
            blue += 1
        else:
            white += 1
    else:
        half = n//2
        cut(x, y, half)
        cut(x+half, y, half)
        cut(x, y+half, half)
        cut(x+half, y+half, half)

n = int(input())
paper= []
for _ in range(n):
    paper.append(list(input().split()))

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

1차 코드에서는 cut 함수에서 종이를 잘라 각각의 종이를 체크한 후 조건을 만족시키지 못하면 cut을 호출했다. 수정 후에는 cut 함수에서 현재 종이의 시작 위치와 크기를 전달 받은 후, 현재 종이만 체크하고 조건에 맞지 않는다면 4개로 나눠 각각 cut을 호출한다.

 

같은 방식이지만 코드 길이와 실행 시간이 조금 개선되었다.