[Python] 2630 색종이 만들기

📌 문제

아래 <그림 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과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

문제를 보면 매번 4개의 섹션으로 분할한다. 즉, 문제를 여러 개로 분할하여 정보를 획득하는 것이다. 큐를 통해서 BFS로 풀이를 할 수도 있지만, 분할 정복으로 풀이하는 것이 더 코드를 명확하게 작성할 수 있으며, 시간 소요를 줄일 수 있다.

분할 정복을 하기 위해서 매개변수를 어떻게 설정할지 정해야 한다. 색종이를 탐색하기 위해서는 어떻게 해야 할까? 좌표를 통해 탐색해야 한다. 즉, 좌표 매개변수가 필요하며, 그 좌표를 통해 얼마나 탐색할지도 정해야 한다. 그렇기 때문에 개수를 담을 매개변수도 하나 설정한다. 그래서 의사코드로 작성하면

def 분할정복(x좌표, y좌표, n 개수):
    for i in range(x좌표, x좌표 + n 개수):
        for j in range(y좌표, y좌표 + n 개수):

이렇게 대강의 순서를 파악했으면 한 색깔로만 이루어졌는지도 확인해야 한다.

바로 떠오르는 것은 white를 0, blue로 1 설정해 순회한 다음 합이 0이거나 n²일 때 각 색종이의 개수를 늘리는 방법이 있다. 하지만, 2중 반복문으로 하나하나 전부 탐색하다보면 시간이 많이 소요될 것이다. 그래서 맨 처음 시작하는 곳의 색을 저장해둬서 그 색과 다른 색을 한 번이라도 발견하면 다시 분할하는 방법이 있다. 만약 분할하지 않는다면 온전한 색종이라는 것이며 white 혹은 blue 색종이의 카운트를 높이면 된다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

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

white = 0
blue = 0

def find_paper(x, y, n):
    global white, blue
    paper = color[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if paper != color[i][j]:
                find_paper(x, y, n // 2)
                find_paper(x + n // 2, y, n // 2)
                find_paper(x, y + n // 2, n // 2)
                find_paper(x + n // 2, y + n // 2, n // 2)
                return

    if paper == 0:
        white += 1
        return
    else:
        blue += 1
        return

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

📄 준비

import sys
input = sys.stdin.readline

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

white = 0
blue = 0

입력이 많기 때문에 sys 모듈을 불러온다. n에 값을 받은 다음에 readlines를 나중에 써서 color에 저장한 다음 color = list(map(lambda x: list(map(int, x.split())), color))로 받으면 4ms 정도 빠르긴 하다. 복잡하지만 더 효율적으로 제출하기 위해서 사용해도 좋다.

white와 blue는 색종이들의 개수를 저장하기 위해 세운 변수이다.

📄 풀이

def find_paper(x, y, n):
    global white, blue
    paper = color[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if paper != color[i][j]:
                find_paper(x, y, n // 2)
                find_paper(x + n // 2, y, n // 2)
                find_paper(x, y + n // 2, n // 2)
                find_paper(x + n // 2, y + n // 2, n // 2)
                return

    if paper == 0:
        white += 1
        return
    else:
        blue += 1
        return

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

find_paper라는 함수를 설정했다. white와 blue의 값을 재할당하며 카운팅하기 때문에 global레벨로 변수를 설정한다.

paper 변수는 동일한 색종이인지 판별하기 위해서 세운 변수이다. for 반복문으로 순회하면서 이것과 다른 값이 있다면 온전한 색종이가 아닌 것이기 때문에 분할 정복을 실시한다. 만약 순회를 모두 통과한다면 온전한 색종이이기 때문에 색깔에 따라 white와 blue 값을 조절한다.

📌 총평

분할 정복의 근본격인 문제이다. 그런데 확실히 분할 정복은 난이도가 극과 극이라서 어렵다 ㅠㅠ